LeetCode 0123. Best Time to Buy and Sell Stock III【Hard】【Python】

Problem

LeetCode

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
             Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Copy the code

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.
Copy the code

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Copy the code

The problem

Power button

Given an array, its ith element is the price of a given stock on day I.

Design an algorithm to calculate the maximum profit you can make. You can make up to two deals.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: If you buy on day 4 (stock price = 0) and sell on day 6 (stock price = 3), the exchange will make a profit = 3-0 = 3. Then, by buying on day 7 (stock price = 1) and selling on day 8 (stock price = 4), the exchange makes a profit of 4-1 = 3.Copy the code

Example 2:

Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3:

Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

Train of thought

Dynamic programming

Find the equation of state dp [I] [k] [0] = Max (dp [I - 1] [k] [0], dp [k] [I - 1] [1] + prices [I]) : Dp [I][k] = Max (dp[i-1][k][1], dp[i-1][k][0] -prices [I]case: dp [1] [k] [0] = dp [I] [k] [0] = 0 dp [1] [k] [1] = dp [I] [k] [1] = - inf because k k = 2 to 2, so k to be exhaustive. dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i]) dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i]) dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]) dp[i][1][1] = max(dp[i-1][1][1], -prices[I]) dp[i-1] is invalid when I = 0. dp[0][1][0] = max(dp[-1][1][0], dp[-1][1][1] + prices[i]) = max(0, -infinity + prices[i]) = 0 dp[0][1][1] = max(dp[-1][1][1], dp[-1][1][0] - prices[i]) = max(-infinity, 0 - prices[i]) = -prices[i] dp[0][2][0] = max(dp[-1][2][0], dp[-1][2][1] + prices[i]) = max(0, -infinity + prices[i]) = 0 dp[0][2][1] = max(dp[-1][2][1], dp[-1][2][0] - prices[i]) = max(-infinity, 0 - prices[i]) = -prices[i]Copy the code

Space complexity: O(1)

Python3 code
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp_i_2_0, dp_i_1_0 = 0.0
        # dp_i_2_1, dp_i_1_1 = -prices[0], -prices[0
        dp_i_2_1, dp_i_1_1 = float('-inf'), float('-inf')  # minus infinity
        for i in range(len(prices)):
            # Yesterday there were no stocks, yesterday there were stocks to sell today
            dp_i_2_0 = max(dp_i_2_0, dp_i_2_1 + prices[i])
            # Yesterday there were stocks, yesterday there were no stocks to buy today
            dp_i_2_1 = max(dp_i_2_1, dp_i_1_0 - prices[i])
            # Yesterday there were no stocks, yesterday there were stocks to sell today
            dp_i_1_0 = max(dp_i_1_0, dp_i_1_1 + prices[i])
            # Yesterday there were stocks, yesterday there were no stocks to buy today
            dp_i_1_1 = max(dp_i_1_1, -prices[i])
            
        return dp_i_2_0
Copy the code

The code address

Making a link

reference

A method solves six stock problems