.买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你能选择某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。不限制买卖次数,问最大盈利,编写一个Java程序
时间: 2024-05-04 18:18:47 浏览: 7
题目可以使用贪心算法来解决。我们可以从第一天开始,如果当天的价格比前一天高,就在前一天买入,当天卖出,这样可以保证每次交易都是在最优的时机进行的。具体实现如下:
```java
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1]) { // 如果当天价格高于前一天价格
profit += prices[i] - prices[i-1]; // 在前一天买入,当天卖出
}
}
return profit;
}
```
时间复杂度为 O(n),空间复杂度为 O(1)。
相关问题
给定一个数组 prices ,它的第 i 个元素prices[i] 表示一支给定股票第 i 天的价格。 你只能选择某一天买入这只股票,并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
### 回答1:
题目要求设计一个算法,能够求出给定一个数组 prices,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票,并选择在未来的某一天卖出该股票。设计一个算法来计算你所能获得的最大利润。如果你不能获得任何利润,返回 0。
具体实现方法可以通过遍历数组来找到数组中最小的数,然后再寻找它之后的最大值,两者相减即为所求的利润最大值,如果没有利润,则返回值为0。可以通过交易中获得的最大利润来证明算法的正确性。
### 回答2:
这道题目是一道典型的贪心算法,并且有一个非常巧妙的办法可以在遍历过程中同时计算出最大利润。
我们记录两个整数变量 minPrice 和 maxProfit,其中 minPrice 表示数组 prices 中当前遍历到的最小值,而 maxProfit 表示当前最大利润。遍历数组时,我们每遍历到一个数字,就用当前价格减去 minPrice 得到一个当前的利润,并将这个利润和当前的 maxProfit 取一个最大值,然后继续向后遍历。如果当前价格比 minPrice 还要小,那么我们就更新 minPrice 为当前价格,因为我们希望能够在价格最低的时候买入。
最后遍历完成后,maxProfit 就是我们要求的最大利润。如果 maxProfit 小于等于 0,那么说明我们无法获取任何利润,因此返回 0。
下面给出 Java 代码实现:
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else {
maxProfit = Math.max(maxProfit, prices[i] - minPrice);
}
}
return maxProfit;
}
}
### 回答3:
题目描述
给定一个数组prices,它的第i个元素prices[i]表示一支给定股票第i天的价格。你只能选择某一天买入这只股票,并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回0。
思路分析
本题可以使用贪心算法来解决。假如我们在买入时选择在最低点购买,那么在之后的每一天里,只要股票价格高于买入价,我们就可以选择在当前天卖出股票,获取最大利润。
因此,我们只需要通过一次遍历数组,找到最低点和最高利润即可。假设low表示当前最低点,max_profit表示当前最高利润,那么对于数组中的每一个元素,我们不断更新low和max_profit即可。
代码实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() <= 1) { // 特判数组长度小于等于1的情况
return 0;
}
int low = prices[0]; // 初始化最低价格为数组的第一个元素
int max_profit = 0; // 初始化最大利润为0
for(int i = 1; i < prices.size(); i++) {
if(prices[i] < low) { // 如果当前价格低于最低价格,更新最低价格
low = prices[i];
}else { // 如果当前价格高于最低价格,计算当前利润并更新最大利润
int cur_profit = prices[i] - low;
if(cur_profit > max_profit) {
max_profit = cur_profit;
}
}
}
return max_profit;
}
};
使用kotlin解决这个问题:121. 买卖股票的最佳时机 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。 示例 1: 输入:[7,1,5,3,6,4] 输出:5 解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。 示例 2: 输入:prices = [7,6,4,3,1] 输出:0 解释:在这种情况下, 没有交易完成, 所以最大利润为 0。 提示: 1 <= prices.length <= 105 0 <= prices[i] <= 104
可以使用动态规划的方法来解决此问题。定义状态 dp[i] 表示前 i 天的最大利润,其中第 i 天可以卖出股票,也可以不卖出股票。因此,状态转移方程为:
```
dp[i] = max(dp[i-1], prices[i]-minPrice)
```
其中,minPrice 表示前 i 天的最低股票价格。
最终的答案就是 dp 数组中的最大值。
下面是使用 Kotlin 实现的代码:
```kotlin
fun maxProfit(prices: IntArray): Int {
var minPrice = Int.MAX_VALUE
var maxProfit = 0
for (price in prices) {
minPrice = minOf(minPrice, price)
maxProfit = maxOf(maxProfit, price - minPrice)
}
return maxProfit
}
```
可以通过以下代码进行测试:
```kotlin
fun main() {
val prices1 = intArrayOf(7, 1, 5, 3, 6, 4)
val prices2 = intArrayOf(7, 6, 4, 3, 1)
println(maxProfit(prices1)) // 5
println(maxProfit(prices2)) // 0
}
```
时间复杂度为 O(n),空间复杂度为 O(1)。