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.
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 .
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
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]
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