122_买卖股票的最佳时机_II

类型：数组

1. 买卖股票的最佳时机 II 💚 ⭐
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/

❓ 数组 prices 存储了股票每天的价格。你可以进行多次交易，但是每次买入股票前必须先卖出手里的股票。求最大收益。

💡 动态规划

每天交易结束后，有两种可能的状态：手中不持有股票，手中持有一支股票

dp[i][0] 表示不持有股票的收益，dp[i][1] 表示持有股票的收益。

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

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

由于在 dp 数组中，dp[i] 只与 dp[i - 1] 有关，因此只要保存前一天的数据即可。
```
class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int dp0 = 0, dp1 = -prices[0];
        for (int i = 1; i < n; ++i) {
            int newDp0 = Math.max(dp0, dp1 + prices[i]);
            int newDp1 = Math.max(dp1, dp0 - prices[i]);
            dp0 = newDp0;
            dp1 = newDp1;
        }
        return dp0;
    }
}
```
💡 贪心

既然购买没有限制，也没有手续费，那我们把所有能盈利的区间全收益了。即把股票走势中所有的上坡段的收益全取了。
```
class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int n = prices.length;
        for (int i = 1; i < n; ++i) {
            ans += Math.max(0, prices[i] - prices[i - 1]);
        }
        return ans;
    }
}
```
时间复杂度：O(n)，空间复杂度：O(1)