Given an array , It's the first i Element (s) of a given stock i Sky price .
If you are allowed to complete at most one transaction （ Buy and sell a stock ）, Design an algorithm to calculate the maximum profit you can get .
Note that you can't sell shares before you buy them .
Input : [7,1,5,3,6,4]
Output : 5
explain : In the 2 God （ Stock price = 1） Buy when , In the 5 God （ Stock price = 6） Sell when , Maximum profit = 6-1 = 5 .
Note that profit cannot be 7-1 = 6, Because the selling price needs to be higher than the buying price .
Input : [7,6,4,3,1]
Output : 0
explain : under these circumstances , No deal is done , So the biggest profit is 0.
We can set two variables , A variable represents the current minimum price , A variable represents the current maximum profit . Traverse the array , First update the minimum price so far , Then subtract the current minimum price from the current price （ profits ）, Update maximum profit based on this . After traversing the array , Return to the maximum profit .
class Solution: def maxProfit(self, prices: List[int]) -> int: minPrice = float("inf") maxProfit = 0 if len(prices) == 0: return 0 for num in prices: if num < minPrice: minPrice = num if num - minPrice > maxProfit: maxProfit = num - minPrice return maxProfit
This kind of stock problem involves the number of times a stock can be traded , Because of the restrictions on the number of stock transactions , You can't just buy and sell , But this problem limits the number of stock transactions k by 1, Therefore, in the process of deriving the state transition equation , When k be equal to 0 when ,dp[i] = 0, That is to say, the profit from not buying or selling stocks or holding stocks is 0. In the course of derivation, others involve k The place of , All are k=1, therefore k It doesn't affect the transition between States .
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 dp = -prices for i in range(1,n): dp[i] = max(dp[i-1],dp[i-1] + prices[i]) dp[i] = max(dp[i-1],-prices[i]) return dp[n-1]
Like any other dynamic planning , The transition between states depends only on two adjacent states , So you don't have to create a two-dimensional array , Just record two adjacent states , Is the space complexity reduced to o(1).
class Solution: def maxProfit(self, prices: List[int]) -> int: if len(prices) == 0: return 0 n = len(prices) dp_0_0 = 0 # Don't hold dp_0_1 = -prices # hold for i in range(1,n): dp_0_0 = max(dp_0_0,dp_0_1 + prices[i]) dp_0_1 = max(dp_0_1,-prices[i]) return dp_0_0