05贪心：买卖股票的最佳时机 II

05贪心：买卖股票的最佳时机 II

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

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

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

如何分解呢？

假如第 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 profit = 0;
        int sumProfit = 0;
        int pre = prices[0];//记录上一次的价格

        for(int i = 1; i < prices.length; i++) {
            profit = prices[i] - pre;
            if(profit > 0) {
                sumProfit += profit;
            }
            pre = prices[i];//更新前面的价格，我需要的是每天的利润，抛弃负利润,那7 1 5距离pre=7，now=1，为-6抛弃的，所以更新pre，不加利润，就是不要7买1卖，接着就是看1,5，正利润所以要加上要1买5卖
        }

        return sumProfit;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18