123. Best time to buy and sell stocks III
Given an array, its first element is the price of a given stock on day i.
Design an algorithm to calculate the maximum profit you can make.You can complete up to two transactions.
**Note: ** You cannot participate in multiple transactions at the same time (you must sell your previous shares before buying again).
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: On day 4 (stock price) = 0)Buy on day 6 (stock price) = 3)When it's time to sell,
The exchange is profitable = 3-0 = 3 .
Then, on the 7th day (stock price) = 1)Buy when you want,
On day 8 (stock price) = 4)When you sell it, the exchange will make a profit = 4-1 = 3 .
dynamic programming
State Definition: dp[i][j][k] indicates the number of cash we have in the [0, i] interval (where the state has a prefix nature), where transactions take place J times, and where the state is K.The meanings of J and K are as follows:
- j = 0 means no transaction occurred;
- j = 1 indicates that there has been a stock purchase at this time;
- j = 2 indicates that there have been two stock purchases at this time.
That is, we artificially record a transaction when we buy stocks.
- k = 0 is not currently owned;
- k = 1 is the current share.
Derive the state transfer equation:
The State Transition Equation can be represented by the following diagram. It is characterized by either doing nothing or moving backwards, that is, the state cannot be reverted.
See the code comments for the specific expression.
Think Initialization:
The initial value of 0, 1, 2 transactions and 0 and 1 status should be set as follows:
- dp[0][0][0] = 0: This is obvious;
- dp[0][0][1]: Indicates that none of the transactions took place, but that it is not possible to hold shares
- dp[0][1][0] = 0: Indicates that a transaction has occurred but that no shares are held, which is not possible.
- Dp[0][1] = -prices[0]: indicates that a transaction has occurred and that we hold shares, so the cash we hold is the opposite of the stock price on that day;
- dp[0][2][0] = 0: Indicates that two transactions have occurred but that no shares are held, which is not possible.Setting to 0 does not affect the optimal value, although it does not make sense.
- dp[0][2][1] =Negative Infinity: Indicates that there have been two transactions and that the stock is held, which is not possible.Note: Although not meaningful, it cannot be set to 0,
The last day when you don't own shares is likely to be the most profitable.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
if n<2:
return 0
# Define a three-dimensional array: day i, how many transactions were made, current buying and selling status
# The 2nd dimension of 0 is meaningless, 1 means the transaction was made once, 2 means the transaction was made twice
# To make values 1 and 2 of the second dimension meaningful, set the length of the second dimension to 3 here
dp = [[[0 for _ in range(2)] for _ in range(3)] for _ in range(n)]
# Understand the following initializations
# The third dimension specifies that shares must be held, so it is -prices[0]
dp[0][1][1] = -prices[0];
#Trading that hasn't happened yet should be initialized to negative infinity when holding shares
dp[0][2][1] =-float('inf')
for i in range(1,n):
dp[i][1][1] = max(dp[i - 1][1][1], -prices[i] )#A deal has occurred and shares are held
dp[i][1][0] = max( dp[i - 1][1][0] , dp[i - 1][1][1] +prices[i] )#A deal has occurred and no shares are held
dp[i][2][1] =max(dp[i-1][2][1], dp[i][1][0] - prices[i]) #There were two transactions and stock holdings
dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i] )#Two transactions occurred and no shares were held
return max(dp[-1][1][0],dp[-1][2][0])
Spatial optimization
Since only yesterday's status is referenced today, removing the first dimension directly will not affect the correctness of the state transition)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
if n<2:
return 0
dp = [[0 for _ in range(2)] for _ in range(3)]
# Dimension 2 specifies the required share ownership, so it is -prices[0]
dp[1][1] = -prices[0];
#Trading that hasn't happened yet should be initialized to negative infinity when holding shares
dp[2][1] =-float('inf')
for i in range(1,n):
dp[1][1] = max(dp[1][1], -prices[i])
dp[1][0] = max(dp[1][0], dp[1][1]+prices[i])
dp[2][1] = max(dp[2][1], dp[1][0]-prices[i])
dp[2][0] = max(dp[2][0], dp[2][1]+prices[i])
return max( dp[2][0] ,dp[1][0] )
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
buy1 = buy2 = -prices[0] #Buy in
sell1 = sell2 = 0 # Sell out
for i in range(1, n):
buy1 = max(buy1, -prices[i])
sell1 = max(sell1, buy1 + prices[i])
buy2 = max(buy2, sell1 - prices[i])
sell2 = max(sell2, buy2 + prices[i])
return sell2