LeetCode刷题：贪心算法 [122.买卖股票的最 佳时机 II] - Java版本

LeetCode刷题：贪心算法 [122.买卖股票的最 佳时机 II] - Java版本

贪心算法：区间问题

只是记录自己的刷题过程，答案参考过多种题解。

如有错误感谢指正！

参考：① LeetCode 101: A LeetCode Grinding Guide (C++ Version) 作者：高畅 Chang Gao

           ② 代码随想录 (programmercarl.com) 作者：程序员Carl

题目来源：题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台 (leetcode-cn.com)

自己的思路：选一个低的买入，在选个高的卖，在选一个低的买入.....循环反复。

结果：太麻烦了，且具体实现有很多bug。

// 实现不了，有数组越界的空指针异常
while (i < prices.length) {
    if (start >= prices[i]) {
    	start = prices[i++];
    } else {
        int end = prices[i];
        while (i < prices.length) {
            ······

• 最终利润可以分解为每天收益情况的总和。假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

• 把利润分解为每天为单位的维度，而不是整体区间去考虑！那么根据prices可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

• 第一天没有利润，至少要第二天才会有利润，所以利润的序列比股票序列少一天。

• 从图中可以发现，其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。那么只收集正利润就是贪心所贪的地方！

• 局部最优：收集每天的正利润；全局最优：求得最大利润。

public int maxProfit(int[] prices) {
int sum = 0;
    for (int i = 1; i < prices.length; i++) {
    	sum += Math.max(prices[i] - prices[i - 1], 0); //只收集每天的正利润
    }
    return sum;
}