使用贪心算法来解决此问题,通过在价格上涨的每一天买入并在第二天卖出的方式,累计所有上涨的利润,以实现最大收益。关键点是从第二天开始遍历,并且只要当前比前一天价格高,我们就在前一天买入然后第二天卖出去。下面是详细的解释:
代码解释
-
初始化变量
maxProfit
:用来存储最大利润,初始值为0。 -
遍历价格数组:从第二天(索引1)开始,遍历
prices
数组。 -
判断今天的价格是否高于昨天的价格:
- 如果今天的价格高于昨天的价格,则意味着在昨天买入、今天卖出可以获得利润。
- 因此,将今天与昨天的价格差(即
prices[i] - prices[i - 1]
)加入maxProfit
中。
-
返回最终的最大利润
maxProfit
。
算法思想
该算法的核心思想是贪心算法,即在每一个局部上涨的区间内进行买卖操作,这样可以保证累积的利润最大化。
- 在股票价格上涨的每个区间段内,只要当天的价格高于前一天,就进行“买入前一天、卖出当天”的操作。
- 这样做的效果等同于在每个连续上涨的区间段的最低点买入、最高点卖出,而无需精确地去找到每个区间的最低和最高点。
- 最终通过一次遍历,累积所有上涨区间的利润,即可获得最大收益。
时间复杂度
该算法的时间复杂度是 (O(n)),其中 (n) 是价格数组的长度,因为只需要遍历一次数组。
java实现
class Solution {
public int maxProfit(int[] prices) {
int maxprofit = 0;
for(int i = 1; i < prices.length; ++i) {
if(prices[i - 1] < prices[i]) {
maxprofit += prices[i] - prices[i - 1];
}
}
return maxprofit;
}
}