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

A good function 2020-11-13 02:57:01

## 1. Title Description

Given an array , It's the first i An element is a given stock in the i Sky price .

Design an algorithm to calculate the maximum profit you can get . You can do at most k transaction .

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 : [2,4,1], k = 2
Output : 2
explain : In the 1 God ( Stock price = 2) Buy when , In the 2 God ( Stock price = 4) Sell when , The exchange will make a profit = 4-2 = 2 .

Example 2:

Input : [3,2,6,5,0,3], k = 2
Output : 7
explain : In the 2 God ( Stock price = 2) Buy when , In the 3 God ( Stock price = 6) Sell when , The exchange will make a profit = 6-2 = 4 .
And then , In the 5 God ( Stock price = 0) Buy when , In the 6 God ( Stock price = 3) Sell when , The exchange will make a profit = 3-0 = 3 .

## 2. Ideas （ Dynamic programming ）

In the third question in the stock series ,, The required number of stock transactions is 2. And in this question is the number of stock transactions k For any value . So you can directly use the code of the previous question ： The best time to buy and sell stocks |||
But it needs to be optimized , Otherwise, it will overrun the memory .

###### Optimize

Consider a stock sale , Buy on the first day , Sell the next day , So a stock trade takes two days . When given k Greater than len(prices)//2 when , As long as the price of the next day is greater than the price of the previous day , Just a stock deal . Anyway, it will not exceed the limit of the number of stock transactions . When k Less than len(prices)//2 when , You can use the code from the previous question , But it needs to be fixed .

### 2.1 python Code

``````class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if len(prices) == 0:
return 0
if k >= len(prices)//2:
profit = 0
for i in range(len(prices)-1):
if prices[i+1] > prices[i]:
profit += (prices[i+1]-prices[i])
return profit
else:
n = len(prices)
dp = [[[0 for i in range(2)] for i in range(k+1)] for i in range(n)]
for i in range(k+1):
# No matter k Equal to several , The first 0 Day does not hold the stock the profit is 0, The profit from holding shares is -prices（ Money to sell stocks ）
dp[i] = 0
dp[i] = -prices
for i in range(1,n):
for j in range(1,k+1):
dp[i][j] = max(dp[i-1][j],dp[i-1][j] + prices[i])
dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] - prices[i])
return dp[n-1][k]
``````