刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-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 * 104
• 0 <= prices[i] <= 104

思路

贪心算法

其实最开始的想法就是对比每天和前一天的价格，有上涨就买，没有就不买。
代码很好写出来，肯定是贪心的思路，但是要证明确实这个解就是最优解其实只是能够无法举出反例而已。

感兴趣可以看下官方题解，有推导证明过程。

动态规划

动态规划其实也是可以解出的。

难度其实在于动态规划数组的定义

• 每一天的状态其实都有两种可能，且这两种可能都会对后续产生影响，所以一维的数组并不能解决问题，每天的两个状态都需要纳入范围。

dp1[i] 意为第 i 天手里有股票时的最大利润
dp0[i] 意为第 i 天手里无股票时的最大利润

• 状态转移方程并不复杂了

dp0[i] =max{dp0[i−1], dp1[i−1]+prices[i]}
dp1[i] =max{dp1[i−1], dp0[i−1]-prices[i]}
当然，从状态转移方程也就能看出来，其实只需要记录前一天的值就够了，所以在不需要记录路径的情况下，可以将动态规划数组简化为两个变量即可。

• 初始数据就是第一天了，没有之前的数据，也就是，当天没股票最大利润就是 0，有股票那就是 价格的负数

剩下的就简单了。老样子，细节在代码注释

代码

贪心

func maxProfit(prices []int) int {
    res := 0
    for i := 1; i < len(prices); i++ {
        // 只看跟前一天的价格差即可，为正则加入
        if prices[i] > prices[i-1] {
            res += prices[i] - prices[i-1]
        }
    }
    return res
}

动态规划

func maxProfit(prices []int) int {
    n := len(prices)
    dp0, dp1 := 0, -prices[0]
    for i := 1; i < n; i++ {
        // 两者都对后续有影响，但也都只有前一天的数据有参考意义
        dp0, dp1 = max(dp0, dp1+prices[i]), max(dp1, dp0-prices[i])
    }
    return dp0
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}