Leetcode122 timing of buying and selling stocks II

difficulty ： secondary

Title Description

​​​​​​ Power button

Ideas

1. The law of greed （ Add up the price difference of all price rising ranges , The calculation process is the actual transaction process ）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        i = 0
        while i < (len(prices) - 1):
            minprice = prices[i]
            maxprice = prices[i]
            j = i + 1
            while j < len(prices) and prices[j] > maxprice:
                maxprice = prices[j]
                j += 1
            profit += max(0, maxprice-minprice)
            i = j
            #print("j:",j,"profit:",profit)
        return profit

2. Dynamic programming （ Refer to the official answer ）https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/

1） Define the State

dp[i][0]: The first i There is no maximum profit of stocks after trading for days

dp[i][1]: The first i The maximum profit of holding stocks after days of trading

2） Transfer equation

Ruodi i No stock , Then the maximum profit is i-1 The biggest profit when there is no stock , Or the third i-1 One day there are stocks , The first i The biggest profit from selling in one day . The first i Days to sell to get prices[i] The profits of the .

dp[i][0]=max{dp[i−1][0],dp[i−1][1]+prices[i]}

Ruodi i One day there are stocks , Then the maximum profit is i-1 The biggest profit when there are shares in the sky , Or the third i-1 No stock , The first i The biggest profit of day buying . The first i Day buying decreases prices[i] The profits of the .

dp[i][1]=max{dp[i−1][1],dp[i−1][0]−prices[i]}

3） The initial state

dp[0][0]=0,dp[0][1]=-prices[0]

4） Code

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp0 = 0
        dp1 = -prices[0]
        for i in range(len(prices)):
            newdp0 = max(dp0, dp1+prices[i])
            newdp1 = max(dp1, dp0-prices[i])
            dp0 = newdp0
            dp1 = newdp1
        return dp0