[数据结构与算法]122. 买卖股票的时机II——动态规划

方法一 动态规划

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        int dp[size][2];
        dp[0][0] = 0;   //第 i 天交易完后手里没有股票的最大利润
        dp[0][1] = -prices[0];  //表示第 i 天交易完后手里持有一支股票的最大利润
        for(int i = 1; i < size; i++){
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]); //卖股票最大利润，第i - 1天利润与第i - 1天买、第i天卖的利润取max
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); //买股票的最大利润，第i - 1天卖的利润与第i天卖的利润取max
        }
        return dp[size - 1][0];
    }
};

Accepted
200/200 cases passed (0 ms)
Your runtime beats 100 % of cpp submissions
Your memory usage beats 24.93 % of cpp submissions (12.8 MB)

方法二 贪心

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

Accepted
200/200 cases passed (8 ms)
Your runtime beats 47.64 % of cpp submissions
Your memory usage beats 89.67 % of cpp submissions (12.6 MB)