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⁴
0 <= prices[i] <= 10⁴

解法一：回溯（超时）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


func maxProfit(prices []int) int {
    n := len(prices)
    res := 0
    // status represents whether the stock is currently held or not.
    // 1 indicates holding and 0 indicates not holding.
    var backtracking func(idx, profit int, status bool)
    backtracking = func(idx, profit int, status bool) {
        if idx == n {
            if profit > res {
                res = profit
            }
            return
        }
        // no operation
        backtracking(idx+1, profit, status)
        if status {
            // sell stocks
            backtracking(idx+1, profit+prices[idx], false)
        } else {
            // buy stocks
            backtracking(idx+1, profit-prices[idx], true)
        }
    }
    backtracking(0, 0, false)
    return res
}

解法二：动态规划

规定：dp[i][j] 记录的是前 i 天持股状态为 j 时能够获得的最大利润。j 的取值为 0 或 1，j==0 表示未持股，j==1 表示持股。

由上面的规定可得：

\begin{equation} \begin{cases} \text{dp[i][0]} = max(dp[i-1][1] + prices[i],dp[i-1][0]) \\ \text{dp[i][1]} = max(dp[i-1][1], dp[i-1][0] - prices[i]) \\ \end{cases} \end{equation}

初始时 dp[0][0] = 0、dp[0][1] = -prices[0]

由此可写出如下动态规划代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func max(nums ...int) int {
    ans := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] > ans {
            ans = nums[i]
        }
    }
    return ans
}

func maxProfit(prices []int) int {
    n := len(prices)
    if n < 2 {
        return 0
    }
    dp := make([][2]int, n)
    dp[0][0], dp[0][1] = 0, -prices[0]
    for i := 1; i < n; i++ {
        dp[i][0] = max(dp[i-1][1]+prices[i], dp[i-1][0])
        dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1])
    }
    return dp[n-1][0]
}

优化上面代码，优化后的代码如下所示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func max(nums ...int) int {
    ans := nums[0]
    for i := 1; i < len(nums); i++ {
        if nums[i] > ans {
            ans = nums[i]
        }
    }
    return ans
}

func maxProfit(prices []int) int {
    n := len(prices)
    if n < 2 {
        return 0
    }
    dp := make([][2]int, 2)
    dp[0][0], dp[0][1] = 0, -prices[0]
    for i := 1; i < n; i++ {
        dp[1][0] = max(dp[0][1]+prices[i], dp[0][0])
        dp[1][1] = max(dp[0][0]-prices[i], dp[0][1])
        dp[0] = dp[1]
    }
    return dp[1][0]
}

解法三：贪心算法

1
2
3
4
5
6
7
8
9


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
}