贪心

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

今天股票的价格减去昨天股票的价格，就是今天的涨幅。第一天res = 0; res += 所有的正涨幅。

具体的含义：由于我们有整个prices数组，所以知道整个股票的价格趋势，贪心的地方在于，每次股票价格开始跌落前都出售股票，然后重新购买。这道题目最关键的是利润分解，拆分为每天的利润，然后收集所有正利润。

• April 14, 2024 2:34 AM (GMT+8) 自己写出来的贪心，没有上面的代码精简

动态规划

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/

一个好的解答真的很重要，官方解答一看就秒懂了。

定义状态 dp[i][0] 表示第 i 天交易完后手里没有股票的最大利润， dp[i][1] 表示第 i 天交易完后手里持有一支股票的最大利润（ i 从 0 开始）。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n][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];
    }
};