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 ).
Input : [1,2,3,0,2]
Output : 3
explain : The corresponding transaction status is : [ purchase , sell , Freezing period , purchase , sell ]
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]
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