算法训练营第四十九天|121. 买卖股票的最佳时机 122.买卖股票的最佳时机II

Leetcode121. 买卖股票的最佳时机

文章链接：代码随想录
题目链接：121. 买卖股票的最佳时机

思路：这种做法（自己做的）是直接取第 i 天的最大收益，而随想录上的做法是把每天分成持有和不持有两种状态并分别记录，最后取最后一天不持有的值。

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

Leetcode122.买卖股票的最佳时机II

文章链接：代码随想录
题目链接：122.买卖股票的最佳时机II

思路：和上一题一样的道理，就是把收益累加起来了。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> dp(prices.size());

        for (int i = 1; i < prices.size(); i++){
            dp[i] = dp[i - 1] + max(prices[i] - prices[i - 1], 0);    
        }
        
        return dp[prices.size() - 1];
    }
};

第四十九天打卡，加油！！！