Best Time to Buy and Sell Stock II

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Tags: array, greedy

承接着上一题的思路，还是想用动态规划来做。这次学乖了，先判断数组的大小，小于等于一的话直接输出0.

逆向遍历数组，分两种情况讨论：

1. 如果当前价格大于下一天的价格，开启一次新的交易，当前profit加到sum里，profit清零；

2. 如果当前价格小于下一天的价格，继续本次交易，更新profit的值。

在最后，把最后一次交易的profit加到sum里。

其实，这道题不用逆向遍历，直接正向遍历，分别比较下一天的价格和当天的价格就好。我逆向遍历是受到了上一题的影响。

所谓动态规划，就是从最简单的情况出发。

我现在想清了，上一题，不必非得用逆向遍历，正向也OK。维护min和max两个变量即可。

重点是，看透问题的本质，什么是最简单的情况，从此入手。

虽然tag里有一个贪婪算法。但我想还是动态规划吧。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int n = prices.size();
        if (n <= 1){
            return 0;
        }
        int sum = 0;
        int profit = 0;
        int nextPrice = *(prices.end() - 1);
        for (int i = n - 2; i >=0; i--){
            if (prices[i] > nextPrice){ // start a new transection
                sum += profit;
                profit = 0;
                nextPrice = prices[i];
            }
            else if (prices[i] <= nextPrice){ // continue this transection
                profit += nextPrice - prices[i];
                nextPrice = prices[i];
            }
        }
        sum += profit;
        return sum;
    }
};

代码运行时间