1. Title Description

Given an array , It's the first i Element (s) of a given stock i Sky price .

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

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 : [7,1,5,3,6,4]
Output : 7
explain : In the 2 God （ Stock price = 1） Buy when , In the 3 God （ Stock price = 5） Sell when , The exchange will make a profit = 5-1 = 4 .
And then , In the 4 God （ Stock price = 3） Buy when , In the 5 God （ Stock price = 6） Sell when , The exchange will make a profit = 6-3 = 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 : under these circumstances , No deal is done , So the biggest profit is 0.

2.1 Conventional thinking

It is allowed to buy and sell many times , So you can buy and sell on the same day or buy on the same day . So as long as the price of the next day is higher than that of the previous day , You can buy and sell . That is, set a variable , Initialize to 0, When the price of the next day is higher than that of the previous day , The variables add up the difference between the prices of the two days .

2.1 python Regular code

class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
profit = 0
for i in range(len(prices)-1):
if prices[i+1] > prices[i]:
profit += (prices[i+1] - prices[i])
return profit

2.2 Dynamic programming

2.2 Dynamic programming code

class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
n = len(prices)
dp = [[0 for i in range(2)] for i in range(n)]
dp[0][0] = 0
dp[0][1] = -prices[0]
for i in range(1,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-1][0]-prices[i])
return dp[n-1][0]

Optimize the code

The spatial complexity of the above dynamic programming can be optimized .

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