【动态规划】代码随想录算法训练营第四十八天 |121. 买卖股票的最佳时机，122.买卖股票的最佳时机II（待补充）

绝地灬酷狼 2024-04-23 04:32 77阅读 0赞

## 121. 买卖股票的最佳时机 ##

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode]

2、文章讲解：[代码随想录][Link 1]

3、题目：

给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

*  示例 1：
 *  输入：\[7,1,5,3,6,4\]
 *  输出：5  
    解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
 *  示例 2：
 *  输入：prices = \[7,6,4,3,1\]
 *  输出：0  
    解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

4、视频链接：

[动态规划之 LeetCode：121.买卖股票的最佳时机1\_哔哩哔哩\_bilibili][LeetCode_121._1_bilibili]

class Solution {
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length == 0) return 0;
            int length = prices.length;
            // dp[i][0]代表第i天持有股票的最大收益
            // dp[i][1]代表第i天不持有股票的最大收益
            int[][] dp = new int[length][2];
            int result = 0;
            dp[0][0] = -prices[0];
            dp[0][1] = 0;
            for (int i = 1; i < length; i++) {
                dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
                dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
            }
            return dp[length - 1][1];
        }
    }

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

1、题目链接：[. - 力扣（LeetCode）][. - _LeetCode 1]

2、文章讲解：[代码随想录][Link 2]

3、题目：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

*  示例 1:
 *  输入: \[7,1,5,3,6,4\]
 *  输出: 7  
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
 *  示例 2:
 *  输入: \[1,2,3,4,5\]
 *  输出: 4  
    解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
 *  示例 3:
 *  输入: \[7,6,4,3,1\]
 *  输出: 0  
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

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

4、视频链接：

[动态规划，股票问题第二弹 | LeetCode：122.买卖股票的最佳时机II\_哔哩哔哩\_bilibili][_ LeetCode_122._II_bilibili]

// 动态规划
    class Solution 
        // 实现1：二维数组存储
        // 可以将每天持有与否的情况分别用 dp[i][0] 和 dp[i][1] 来进行存储
        // 时间复杂度：O(n)，空间复杂度：O(n)
        public int maxProfit(int[] prices) {
            int n = prices.length;
            int[][] dp = new int[n][2];     // 创建二维数组存储状态
            dp[0][0] = 0;                   // 初始状态
            dp[0][1] = -prices[0];
            for (int i = 1; i < n; ++i) {
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);    // 第 i 天，没有股票
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);    // 第 i 天，持有股票
            }
            return dp[n - 1][0];    // 卖出股票收益高于持有股票收益，因此取[0]
        }
    }

##  ##

[. - _LeetCode]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/
[Link 1]: https://www.programmercarl.com/0121.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BA.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[LeetCode_121._1_bilibili]: https://www.bilibili.com/video/BV1Xe4y1u77q
[. - _LeetCode 1]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
[Link 2]: https://www.programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
[_ LeetCode_122._II_bilibili]: https://www.bilibili.com/video/BV1D24y1Q7Ls