代码随想录 Day27 贪心02上 LeetCode T122 买卖股票的最佳时机 II

LeetCode T122 买卖股票的最佳时机II

题目链接:122. 买卖股票的最佳时机 II - 力扣（LeetCode）

题目思路:

这题的基本思路还是使用贪心算法,有人可能还在思考啥是贪心算法,这个算法就是你提出一个思想,且找不到明显的反例,这个思路就可以一试,这道题的局部最优就是后一天减去前一天的结果大于0,全局最优就是利润最多,所以我们就有一个思路,for循环从0开始遍历这个数组,只要每次取出两天中的股票差和前一天作比较,如果>0就加入累计和里,小于0则不做处理,最后就能得到所求答案了.

更好理解的解释:

这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入.....循环反复。

如果想到其实最终利润是可以分解的，那么本题就很容易了！

如何分解呢？

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

题目代码:

class Solution {
    public int maxProfit(int[] prices) {
        int maxP = 0;
        for(int i = 0;i<prices.length-1;i++)
        {
            maxP += Math.max(prices[i+1] - prices[i],0);
        }
        return maxP;
    }
}