题目描述：

方法1：二维dp动态规划

dp[i][0]，表示第i天拥有股票最大收益

dp[i][1]，表示第i天没有股票最大收益

dp[i][0] = max(dp[i-1][0], -price[i])

• 第i-1天就持有股票，那么就保持现状

• 第i天买入股票

dp[i][1] = max(dp[i-1][1], dp[i-1][0] + price[i])

• 第i-1天就不持有股票，那么就保持现状

• 第i天卖出股票

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

优化，当天的只与上一天的有关，不需要用到整个数组

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = -prices[i]; //dp[i-1][0]
        int j = 0; //dp[i-1][1]
        int p = 0; //dp[i][0]
        int q = 0; //dp[i][1]

        for(int k=1;k<prices.size();k++){
            p = max(i,-prices[k]);
            q = max(j,prices[k] + i);
            i = p;
            j = q;
        }
        return q;
    }
};