1. Title Description

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.

2. Ideas （ Dynamic programming ）

2.1 python Code

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]

2.2 Optimize the code

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