## Leetcode: the best time to buy and sell stocks (Python)

A good function 2020-11-13 02:57:07
leetcode best time buy sell

## 1. Title Description

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 .

Example 1:

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 .

Example 2:

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

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 .

### 2.1 Python Code

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

## 2.2 Dynamic programming

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

### 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],-prices[i])
return dp[n-1][0]
``````

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

### Dynamically optimize code

``````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[0] # 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
``````