1. Title Description

Given an array of integers , Among them the first i Elements represent the i Day's share price .​

Design an algorithm to calculate the maximum profit . Under the following constraints , You can do as many deals as you can （ Buy and sell a stock many times ）:

You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）.
After sale of shares , You can't buy shares the next day ( That is, the freezing period is 1 God ).

Example :

Input : [1,2,3,0,2]
Output : 3
explain : The corresponding transaction status is : [ purchase , sell , Freezing period , purchase , sell ]

2. Ideas （ Dynamic programming ）

2.1 python Code

class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
n = len(prices)
dp = [[0 for i in range(2)] for j in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
dp[1][0] = max(0,prices[1]-prices[0])
dp[1][1] = max(-prices[0],-prices[1])
for i in range(2,n):
dp[i][0] = max(dp[i-1][0],dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1],dp[i-2][0]-prices[i])
return dp[n-1][0]

Optimize

class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:
return 0
n = len(prices)
dp_cur_0 = 0
dp_cur_1 = -prices[0]
dp_pre_0 = 0
for i in range(1,n):
temp = dp_cur_0
# During state transition , Only those who didn't hold stocks the day before yesterday, as the case may be ,
# Define a temp Variable , The day before the current day , And keep updating 
dp_cur_0 = max(dp_cur_0,dp_cur_1 + prices[i])
dp_cur_1 = max(dp_cur_1,dp_pre_0 - prices[i])
dp_pre_0 = temp
return dp_cur_0