123. Best Time to Buy and Sell Stock III

这次最多只能进行两次交易，求最大收益

Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        # 6 star, todo, 没有理解，几次做错了
        # https://www.hrwhisper.me/leetcode-best-time-to-buy-and-sell-stock-i-ii-iii-iv/
        #  动态规划，dp[i]表示到第i天能获取的最大收益，两次操作的最大收益等于第i天之后的最大价格减去第i天的价格加上dp[i-1]
        # dp[i] = max(dp[i-1], prices[i]-min_price)
        if not prices: return 0
        dp = [0] * len(prices)
        min_price = prices[0]
        for i in range(1, len(prices)):
            dp[i] = max(dp[i - 1], prices[i] - min_price)
            min_price = min(prices[i], min_price)

        ans = dp[-1]
        max_price = prices[-1]
        for i in range(len(prices) - 2, 0, -1):
            ans = max(ans, max_price - prices[i] + dp[i - 1])
            max_price = max(max_price, prices[i])

        return ans

Go:

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
27
28
29
// 6 star, 动态规划
// dp[i]表示到第i天的最大收益, nax_price为最大售价，每次减去price[i]得到第i天之后的利润，加上dp[i – 1]即为两次买卖的值

func maxProfit(prices []int) int {
	length := len(prices)
	if length == 0 {return 0}
	dp := make([]int, length)
	var minPrice = prices[0]
	for i:=1; i<length; i++ {
		if dp[i-1] > prices[i] - minPrice {
			dp[i] = dp[i-1]
		} else {
			dp[i] = prices[i] - minPrice
		}
		if prices[i] < minPrice {minPrice = prices[i]}

	}
	ret := dp[length-1]
	maxPrice := prices[length-1]


	for j := length-1; j > 0; j-- {
		if maxPrice - prices[j] + dp[j-1] > ret {ret = maxPrice - prices[j] + dp[j-1]}
		if prices[j] > maxPrice {maxPrice = prices[j]}

	}
	return ret

}