LeetCode122 买卖股票的最佳时机II

链接： https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

这一题贪心和dp两种解法都可以做。
首先是贪心，只要当前的价格低于之前出现的高价，就在之前的高价处卖出，并在当天买入。
贪心做法：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> dp(prices.size());
        int now = prices[0], total = 0, pre = prices[0];
        for(int i = 1; i < prices.size(); i++) {
            if (prices[i] < now) {
                total += now - pre;
                now = pre = prices[i];
            }
            else {
                now = prices[i];
                if (i == prices.size() - 1) {
                    total += now - pre;
                }
            }
        }
        return total;
    }
};

动态规划做法：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<vector<int>> dp(prices.size());
        for(auto &idx: dp) {
            idx.resize(2);
        }
        dp[0][1] = -prices[0];
        // dp[i][0]表示第i天无股票的最大利润 dp[i][1]表示第i天持有股票的最大利润
        for(int i = 1; i < prices.size(); i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.size() - 1][0];
    }
};