122 买卖股票的最佳时机 II

🔗 相关链接

买卖股票的最佳时机 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

💡 思路

动态规划

由于在任何时候最多只能持有一种股票，那么在第n天交易结束时具有不持有股票和持有股票两种状态，即 dp[n][0] 和 dp[n][1]。 n从0开始计算。

不持有股票时，截止第n天所能获得的最大利润需要参考前一天的状态：

• 若前一天 n-1 持有股票，第n天无股票，则为卖出股票，则 dp[n][0] = dp[n-1][1] + price[n]；
• 若前一天 n-1 不持有股票，第n天无股票，则为无操作，此时截止第n天所获的利润与第n-1天相同，即 dp[n][0] = dp[n-1][0]。

持有股票时：

• 若前一天 n-1 持有股票，第n天持有股票，则为无操作，则 dp[n][1] = dp[n-1][1]；
• 若前一天 n-1 不持有股票，第n天不持有股票，则为买入股票，则 dp[n][1] = dp[n-1][0] - price[n]。

综上：

• dp[n][0] = max(dp[n-1][1] + price[n], dp[n-1][0])
• dp[n][1] = max(dp[n-1][0] - price[n], dp[n-1][1])

算出最后一天的 dp[n][0] 即可。

根据定义：dp[0][0] = 0, dp[0][1] = -price[0]。

贪心

由于交易次数不受限，所以计算每一个 price[i] - price[i-1] > 0 的总和即可。

💻 代码实现

动态规划

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

贪心

public int maxProfit(int[] prices) {
    int sum = 0;
    for (int i = 1; i < prices.length; i++) {
        int res = prices[i] - prices[i - 1];
        if (res > 0) {
            sum += res;
        }
    }
    return sum;
}