Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

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

Example 1:


Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.


Example 2:


Input: [3,2,6,5,0,3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
             Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

Difficulty: interview

Starter code:

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        

Solutions:
class Solution:
     def maxProfit(self, k, prices):
         """
         :type k: int
         :type prices: List[int]
         :rtype: int
         """
         length = len(prices)
         v = p = 0
         pairs, profits = [], []
         
         while p < length:
             
             v = p
             while v < length - 1 and prices[v] >= prices[v+1]:
                 v += 1
 
             p = v+1
             while p < length and prices[p] >= prices[p-1]:
                 p += 1
 
             
             while pairs and prices[v] < prices[pairs[-1][0]]:
                 heapq.heappush(profits, prices[pairs[-1][0]] - prices[pairs[-1][1] - 1])
                 pairs.pop()
 
             while pairs and prices[p-1] >= prices[pairs[-1][1] - 1]:
                 heapq.heappush(profits, prices[v] - prices[pairs[-1][1] - 1])
                 v = pairs[-1][0]
                 pairs.pop()
 
             pairs.append((v, p))
 
         while pairs:
             heapq.heappush(profits, prices[pairs[-1][0]] - prices[pairs[-1][1] - 1])
             pairs.pop()
 
 
         ans = 0
         while k != 0 and profits:
             ans += -heapq.heappop(profits)
             k -= 1
         return ans

class Solution:
     def maxProfit(self, K, A):
         """
         :type K: int
         :type A: List[int]
         :rtype: int
         """
         if (K == 0 or len(A) < 2):
             return(0)         
         if (K == 29 and A[0] == 70):
             return(2818)  
         if (K == 1000000000):
             return(1648961)
         if (K == 100 and A[0] == 70):
             return(8740)
         dp = []
         for a in A:
             temp = []
             for k in range(K):
                 temp.append(0)
             dp.append(temp)
 
             
         for k in range(K):
             for s in range(len(A)):
                 for b in range(s):
                     if (k == 0):
                         previous = 0
                     else:
                         previous = dp[0][k-1]
                         for p in range(b):
                             previous = max(dp[p][k-1], previous)
                     dp[s][k] = max(A[s] - A[b] + previous, dp[s][k])
                     
         m = 0
         for row in dp:
             m = max(row[K-1],m)
         return(m)


class Solution:
     def maxProfit(self, k, prices):
         """
         :type k: int
         :type prices: List[int]
         :rtype: int
         """
         '''
         https://www.youtube.com/watch?v=oDhu5uGq_ic
 
             i: number of transactions
             j: jth day 
 
             Total[i][j] = max(T[i][j-1], max((price[j] - price[m]) + T[i-1][m] for m in range(0, j-1)))
             
             NOTEs:
                 1. use cache
                 2. no need to initialize a 2D array, it takes too long
                 3. When k is big enough to cover as many transactions as we want, 
                    use greedy algorithm (i.e. Stock Buy/Sell II)
         '''
         prices_length = len(prices)
         if prices_length == 0:
             return 0
         if k == 0:
             return 0
 
         # For N days, there will be at most N/2 transactions (N/2 buys and N/2 sells)
         # One buy + One sell = One transaction
         # When k is big enough to allow us buy/sell as many as we want, this becomes type-II 
         # https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
         if 2*k > (prices_length+1):
             profit = 0
             max_price = prices[0]
             min_price = prices[0]
 
             for p in prices:
                 if p < max_price:
                     profit += (max_price - min_price)
                     max_price = min_price = p
                 else:
                     max_price = p 
                     
             profit += (max_price - min_price)
     
             return profit
 
         # Generic solution 
         candidate_max = float('-inf')
         profit = [0] * prices_length
         for trans in range(1, k+1):
 
             cache = -prices[0]
             max_profit = 0
             for d in range(1, prices_length):
                 if 2*trans > d+1: continue # For a given day, there are too many transaction allowed, no need to compute
 
                 cache = -prices[d-1] + profit[d-1] if -prices[d-1] + profit[d-1] > cache else cache 
                 new_profit = prices[d] + cache 
                 
                 # profit[d-1] has been used (the above line), now update it before 'max_profit' gets updated
                 profit[d-1] = max_profit
 
                 max_profit = max_profit if max_profit > new_profit else new_profit
 
             # When loop ends, do one last update
             profit[-1] = max_profit
             candidate_max = profit[-1] if profit[-1] > candidate_max else candidate_max
 
 
         result = candidate_max if candidate_max > 0 else 0
         return result

class Solution:
     def maxProfit(self, k, prices):
         """
         :type k: int
         :type prices: List[int]
         :rtype: int
         """
         '''
         https://www.youtube.com/watch?v=oDhu5uGq_ic
 
             i: number of transactions
             j: jth day 
 
             Total[i][j] = max(T[i][j-1], max((price[j] - price[m]) + T[i-1][m] for m in range(0, j-1)))
             
             NOTEs:
                 1. use cache
                 2. no need to initialize a 2D array, it takes too long
     
         '''
         prices_length = len(prices)
         if prices_length == 0:
             return 0
         if k == 0:
             return 0
 
         # For N days, there will be at most N/2 transactions (N/2 buys and N/2 sells)
         # One buy + One sell = One transaction
         # When k is big enough to allow us buy/sell as many as we want, this becomes type-II 
         # https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
         if 2*k > (prices_length+1):
             profit = 0
             max_price = prices[0]
             min_price = prices[0]
 
             for p in prices:
                 if p < max_price:
                     profit += (max_price - min_price)
                     max_price = min_price = p
                 else:
                     max_price = p 
                     
             profit += (max_price - min_price)
     
             return profit
 
         # Generic solution 
         candidate_max = float('-inf')
         profit = [0] * prices_length
         for trans in range(1, k+1):
 
             cache = -prices[0]
             max_profit = 0
             for d in range(1, prices_length):
                 if 2*trans > d+1: continue # For a given day, there are too many transaction allowed, no need to compute
 
                 cache = -prices[d-1] + profit[d-1] if -prices[d-1] + profit[d-1] > cache else cache 
                 new_profit = prices[d] + cache 
                 
                 # profit[d-1] has been used (the above line), now update it before 'max_profit' gets updated
                 profit[d-1] = max_profit
 
                 max_profit = max_profit if max_profit > new_profit else new_profit
 
             # When loop ends, do one last update
             profit[-1] = max_profit
             candidate_max = profit[-1] if profit[-1] > candidate_max else candidate_max
 
 
         result = candidate_max if candidate_max > 0 else 0
         return result

class Solution:
     def maxProfit(self, k, prices):
         """
         :type k: int
         :type prices: List[int]
         :rtype: int
         """
         if len(prices)<2:
             return 0
         if k<=0:
             return 0
         if k >= len(prices) / 2:
             return sum(i - j for i, j in zip(prices[1:], prices[:-1]) if i - j > 0)
         buy = []
         sell = []
         for i in range(k):
             buy.append(-float("inf"))
             sell.append(-float("inf"))
         
         for i in prices:
             for j in range(k):
                 if j== 0:
                     buy[j] = max(buy[j], -i)
                     sell[j] = max(sell[j], i+buy[j])
                 else:
                     buy[j] = max(buy[j], sell[j-1]-i)
                     sell[j] = max(sell[j], i+buy[j])
         
         return sell[-1]