188. Best Time to Buy and Sell Stock IV Leetcode Python

Say you have an array for which theithelement is the price of a given stock on dayi.

Design an algorithm to find the maximum profit. You may complete at mostktransactions.

Note:You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Credits:Special thanks to@Freezenfor adding this problem and creating all test cases.

Based on Dynamic planning

maintain two vectors: gpro: to day i the maximum profit

lpro: to day i the maximum profit with jth sell by day i

the complexity of this problem is O(k*n)

code is as follow:

class Solution:# @return an integer as the maximum profitdef helper(self, prices):pro = 0for i in range(len(prices) – 1):pro = max(pro, pro + prices[i+1] – prices[i])return prodef maxProfit(self, k, prices):m = len(prices)if m == 0:return 0if k >= m:### if k >=m this problem become best time to sell IIreturn self.helper(prices)lpro = [0] * (k + 1)gpro = [0] * (k + 1)for i in range(len(prices) – 1):dif = prices[i + 1] – prices[i]j = kwhile j >= 1:lpro[j] = max(gpro[j-1]+max(0,dif), lpro[j] + dif)gpro[j] = max(gpro[j], lpro[j])j-=1return gpro[k]

，任何业绩的质变都来自于量变的积累。