买卖股票的最佳时机Ⅱ

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

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。

返回你能获得的最大利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

解题思路

1.确定dp数组及下标的含义

dp[i] [0] 表示第 i 天持有股票所得的最多现金，不代表今天买入，也可能之前买入，今天保持买入状态

dp[i] [1] 表示第 i 天不持有股票的最多现金，不代表今天卖出，也可能之前卖出，今天保持卖出状态

2.确定递推公式

如果第i天持有股票即dp[i] [0]， 那么可以由两个状态推出来

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1] [0]
• 第i天买入股票，所得现金就是昨天不持有股票的现金减去今天股票的价格：dp[i-1] [1] - prices[i] （这里也是和[买卖股票的最佳时机](./25. 买卖股票的最佳时机.md)唯一的不同特点。）

那么dp[i] [0]应该选所得现金最大的，所以dp[i] [0] = max(dp[i - 1] [0], -prices[i]);

如果第i天不持有股票即dp[i] [1]， 也可以由两个状态推出来

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1] [1]
• 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1] [0]

同样dp[i] [1]取最大的，dp[i] [1] = max(dp[i - 1] [1], prices[i] + dp[i - 1] [0]);

3.初始化dp数组

由递推公式可知，都要从dp[0] [0] 和dp[0] [1] 推导出来

dp[0] [0] -= -prices[0] ，表示第0天就持有股票，买入股票所剩金额为负数

dp[0] [1] = 0，表示第0天不持有股票

4.确定遍历顺序

从前往后遍历

dp数组的状态如图

代码

class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i<prices.length; i++){
            //dp[i][0]表示第i天持有股票所得的最多现金
            //1.dp[i-1][0]表示第i天不买入股票，2.dp[i-1][1]-prices[i]表示第i天买入股票
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]); 
            //dp[i][1]表示第i天不持有股票的最多现金
            //1.dp[i-1][1]表示第i天之前已经卖出股票，2.dp[i-1][0]+prices[i]表示第i天卖出股票
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); 
        }
        return dp[prices.length-1][1];
    }
}

• 时间复杂度：$O(n)$

• 空间复杂度：$O(n)$

dp[i]只是依赖于dp[i - 1]的状态，可以使用滚动数组来节省空间

class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[2];
        dp[0] = -prices[0];
        dp[1] = 0;
        for(int i = 1; i<prices.length; i++){
            dp[0] = Math.max(dp[0], dp[1] - prices[i]); 
            dp[1] = Math.max(dp[1], dp[0] + prices[i]); 
        }
        return dp[1];
    }
}

• 时间复杂度：$O(n)$

• 空间复杂度：$O(1)$

贪心

class Solution {
    public int maxProfit(int[] prices) {
        int[] profit = new int[prices.length - 1];
        //计算如何前一天买入，后一天卖出的盈利
        for(int i = 1; i < prices.length; i++){
            profit[i-1] = prices[i] - prices[i-1];
        }
        int sum = 0;
        //只需要把所有的盈利的正的累计起来，就是最大的利润
        for(int i = 0; i < profit.length; i++){
            if(profit[i] > 0){
                sum += profit[i];
            }
        }
        return sum;

    }
}