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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Data structures

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

Solutions:
class Solution:

	def maxProfit(self, k, prices):
		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):
		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):
		prices_length = len(prices)
		if prices_length == 0:
			return 0
		if k == 0:
			return 0
		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
		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
				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] = max_profit
				max_profit = max_profit if max_profit > new_profit else new_profit
			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):
		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]