## Leecode: the best time to buy and sell stocks, including the freezing period (Python)

A good function 2020-11-13 02:57:00

## 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
dp = -prices
dp = max(0,prices-prices)
dp = max(-prices,-prices)
for i in range(2,n):
dp[i] = max(dp[i-1],dp[i-1]+prices[i])
dp[i] = max(dp[i-1],dp[i-2]-prices[i])
return dp[n-1]
``````

#### 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
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
``````