Given an array , It's the first i An element is a given stock in the i Sky price .
Design an algorithm to calculate the maximum profit you can get . You can do at most Two pens transaction .
Be careful : You can't participate in multiple transactions at the same time ( You have to sell the stock before you buy it again ).
Example 1:
Input : [3,3,5,0,0,3,1,4]
Output : 6
explain : In the 4 God ( Stock price = 0) Buy when , In the 6 God ( Stock price = 3) Sell when , The exchange will make a profit = 3-0 = 3 .
And then , In the 7 God ( Stock price = 1) Buy when , In the 8 God ( Stock price = 4) Sell when , The exchange will make a profit = 4-1 = 3 .
Example 2:
Input : [1,2,3,4,5]
Output : 4
explain : In the 1 God ( Stock price = 1) Buy when , In the 5 God ( Stock price = 5) Sell when , The exchange will make a profit = 5-1 = 4 .
Notice that you can't be in the 1 Day and day 2 Day after day buying stock , Then sell them .
Because it's involved in multiple transactions at the same time , You have to sell the stock before you buy it again .
Example 3:
Input : [7,6,4,3,1]
Output : 0
explain : In this case , No deal is done , So the biggest profit is 0.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
k = 2
n = len(prices)
dp = [[[0 for i in range(2)] for i in range(k+1)] for i in range(n)]
dp[0][1][0] = 0
dp[0][1][1] = -prices[0]
dp[0][2][0] = 0
dp[0][2][1] = -prices[0]
for i in range(1,n):
for j in range(1,3):
dp[i][j][0] = max(dp[i-1][j][0],dp[i-1][j][1] + prices[i])
dp[i][j][1] = max(dp[i-1][j][1],dp[i-1][j-1][0] - prices[i])
return dp[n-1][k][0]
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
k = 2
n = len(prices)
dp_i_1_0 = 0
dp_i_1_1 = -prices[0]
dp_i_2_0 = 0
dp_i_2_1= -prices[0]
for i in range(1,n):
dp_i_1_0 = max(dp_i_1_0,dp_i_1_1 + prices[i])
dp_i_1_1 = max(dp_i_1_1,-prices[i])
dp_i_2_0 = max(dp_i_2_0,dp_i_2_1 + prices[i])
dp_i_2_1 = max(dp_i_2_1,dp_i_1_0 - prices[i])
return dp_i_2_0