leetcode122.买卖股票的最佳时机II

题目链接

题目描述：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

题解：贪心

贪心策略是指，在对问题求解时，将整体的问题划分为一系列局部问题，对局部的问题求出最优解，再通过数学归纳法证明每一步贪心选择最终可以得到问题的一个整体的最优解。
对于给定的数组[a,b,c,d],如果说a <= b <= c <= d，那么股票的最大收益自然是d - a;也就是：(d - c) + (c - b) + (b - a)。
所以，本题的贪心策略为：当访问到一个 prices[i] 并且有 prices[i] - prices[i-1] > 0，那么就把 prices[i] - prices[i-1] 的值添加加到收益中，从而在局部最优的情况下也保证全局最优。具体的证明其实非常繁琐，任何贪心问题的证明都需要花费很久，这里就不给于证明了。

代码如下：

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

时间复杂度：O(N)
额外空间复杂度：O(1)

执行结果：