[数据结构与算法]122. 买卖股票的最佳时机 II

122. 买卖股票的最佳时机 II - 力扣（LeetCode） (leetcode-cn.com)

动态规划：

二维数组用来记录股票收益，当天持有股票最大收益：max(昨天持有今天没卖，或者昨天不持有今天买进)；当天不持有股票最大收益：max(昨天不持有，或者昨天持有今天卖了)。返回第n-1天不持有状态。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0) return 0;
        vector<vector<int>>dp(n,vector<int>(2));
        dp[0][0]=0,dp[0][1]=-prices[0];
        for(int i=1;i<n;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[n-1][0];
    }
};

贪心：

只要昨天的股票比今天的股票价格低就卖出

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