大家好，我是晓星航。今天为大家带来的是 122. 买卖股票的最佳时机 II 相关的讲解！😀

题目简介

题目解答

思路：如果下一天的股票价格高于上一天，直接立即买入第二天卖出，重复操作，到最后即会求得最大利润。

解法一：贪心(遍历数组买入即卖)

代码：

class Solution {
 public int maxProfit(int[] prices) {
        int revenue = 0;
        for (int i = 1; i < prices.length; i++) {
            if(prices[i]>prices[i-1])
                revenue += prices[i]-prices[i-1];

        }
        return revenue;
    }
}

因为这里我们可以多次辗转的买卖股票求最大值，因此我们可以有低价就买入有高价就卖出，最大利润可以为相邻的股票不经过任何等待直接卖出。

复杂度分析：

时间复杂度：O(n)，只需要遍历一次。
空间复杂度：O(1)，只使用了常数个变量。

解法二：动态规划(双数组)

代码：

class Solution {
    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]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[n - 1][0];
    }
}

dp[0][0] = -prices[0] 可能表示在第一天结束时，持有股票的最大利润或成本为第一天股票价格的负值。这是因为在初始状态下，第一天只能买入股票，所以将 dp[0][0] 初始化为第一天股票价格的负值是合理的。

这行代码返回的是在最后一天结束时不持有股票的最大利润，即动态规划数组中 dp 的最后一行第一个元素的值。

复杂度分析：

• 时间复杂度：O(n)，其中 nnn 为数组的长度。一共有 2n 个状态，每次状态转移的时间复杂度为 O(1)，因此时间复杂度为 O(2n)=O(n)。

• 空间复杂度：O(n)。我们需要开辟 O(n) 空间存储动态规划中的所有状态。如果使用空间优化，空间复杂度可以优化至 O(1)。

题目链接

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

感谢各位读者的阅读，本文章有任何错误都可以在评论区发表你们的意见，我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞，你的每一次鼓励都是作者创作的动力哦！😘