In the stock market, a person buys a stock and sells it on some future date. Given the stock prices of N days in an array A[ ] and a positive integer K, find out the maximum profit a person can make in at-most K transactions. A transaction is equivalent to (buying + selling) of a stock and new transaction can start only when the previous transaction has been completed.
Example 1:
Input: K = 2, N = 6
A = {10, 22, 5, 75, 65, 80}
Output: 87
Explaination: 
1st transaction: buy at 10 and sell at 22. 
2nd transaction : buy at 5 and sell at 80.
Example 2:
Input: K = 3, N = 4
A = {20, 580, 420, 900}
Output: 1040
Explaination: The trader can make at most 2 
transactions and giving him a profit of 1040.
Example 3:
Input: K = 1, N = 5
A = {100, 90, 80, 50, 25}
Output: 0
Explaination: Selling price is decreasing 
daily. So seller cannot have profit.
Your Task:
You do not need to read input or print anything. Your task is to complete the function maxProfit() which takes the values K, N and the array A[] as input parameters and returns the maximum profit.
Expected Time Complexity: O(N*K)
Expected Auxiliary Space: O(N*K)
Constraints:
1 ≤ N ≤ 500
1 ≤ K ≤ 200
1 ≤ A[ i ] ≤ 1000

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Mathematics

Starter code: #User function Template for python3

class Solution:
    def maxProfit(self, K, N, A):
        # code here

Solutions:
class Solution:

	def maxProfit(self, K, N, A):
		if K == 0 or N == 0:
			return 0
		dp = [[[0 for _ in range(2)] for _ in range(K + 1)] for _ in range(N)]
		for i in range(N):
			dp[i][0][0] = 0
		for k in range(K + 1):
			dp[0][k][0] = 0
			dp[0][k][1] = -A[0]
		for i in range(1, N):
			for k in range(1, K + 1):
				dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + A[i])
				dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - A[i])
		return dp[N - 1][K][0]


import math

class Solution:

	def maxProfit(self, K, N, A):
		dp = [[0] * (K + 1) for j in range(N + 1)]
		for k in range(1, K + 1):
			pre_diff = -math.inf
			for i in range(1, N + 1):
				pre_diff = max(pre_diff, -A[i - 1] + dp[i - 1][k - 1])
				dp[i][k] = max(pre_diff + A[i - 1], dp[i - 1][k])
		return dp[N][K]


class Solution:

	def maxProfit(self, K, N, A):
		stateMap = [[-float('inf') if i != 0 else 0 for i in range(1 + 2 * K)] for _ in range(N + 1)]
		for r in range(1, N + 1):
			for c in range(K):
				if stateMap[r - 1][2 * c] != -float('inf'):
					stateMap[r][2 * c + 1] = max(stateMap[r - 1][2 * c + 1], stateMap[r - 1][2 * c] - A[r - 1])
					stateMap[r][2 * c + 2] = max(stateMap[r - 1][2 * c + 2], stateMap[r - 1][2 * c + 1] + A[r - 1])
		return max(stateMap[-1])


import numpy as np

class Solution:

	def rec_sol(self, K, N, A, ind):
		if K == 0:
			return 0
		if N - ind < 1:
			return 0
		maxa = -99999
		for i in range(ind + 1, N + 1):
			if A[i - 1] > A[ind - 1]:
				maxa = max(maxa, A[i - 1] - A[ind - 1] + self.rec_sol(K - 1, N, A, i + 1))
		return max(maxa, self.rec_sol(K, N, A, ind + 1))

	def dp_sol(self, K, N, A, ind, dp):
		if K == 0:
			return 0
		if N - ind < 1:
			return 0
		if dp[K][ind] != -1:
			return dp[K][ind]
		maxa = -99999
		for i in range(ind + 1, N + 1):
			if A[i - 1] > A[ind - 1]:
				maxa = max(maxa, A[i - 1] - A[ind - 1] + self.dp_sol(K - 1, N, A, i + 1, dp))
		dp[K][ind] = max(maxa, self.dp_sol(K, N, A, ind + 1, dp))
		return dp[K][ind]

	def dp_sol2(self, K, N, A):
		dp = np.array([[-0] * (N + 1)] * (K + 1))
		for trans in range(1, K + 1):
			curr_balance = dp[trans - 1][1] - A[0]
			for day in range(2, N + 1):
				dp[trans][day] = max(dp[trans][day - 1], A[day - 1] + curr_balance)
				curr_balance = max(curr_balance, dp[trans - 1][day] - A[day - 1])
		return dp[K][N]

	def maxProfit(self, K, N, A):
		return self.dp_sol2(K, N, A)


class Solution:

	def maxProfit(self, K, N, A):
		dp = {}

		def fun(i, k, flag):
			if i == N or k == 0:
				return 0
			if (i, k, flag) in dp:
				return dp[i, k, flag]
			if flag == True:
				dp[i, k, flag] = max(fun(i + 1, k, True), fun(i + 1, k, False) - A[i])
			else:
				dp[i, k, flag] = max(fun(i + 1, k, flag), A[i] + fun(i + 1, k - 1, True))
			return dp[i, k, flag]
		return fun(0, K, True)


class Solution:

	def maxProfit(self, K, N, A):
		dp = {}

		def fun(i, k, flag):
			if i == N or k == 0:
				return 0
			if (i, k, flag) in dp:
				return dp[i, k, flag]
			if flag == True:
				dp[i, k, flag] = max(fun(i + 1, k, True), fun(i + 1, k, False) - A[i])
			else:
				dp[i, k, flag] = max(fun(i + 1, k, flag), A[i] + fun(i + 1, k - 1, True))
			return dp[i, k, flag]
		return fun(0, K, True)

class Solution:

	def maxProfit(self, K, N, A):
		dp = [0] * N
		for tns in range(K):
			(pos, profit) = (-A[0], 0)
			for i in range(1, N):
				pos = max(pos, dp[i] - A[i])
				profit = max(profit, pos + A[i])
				dp[i] = profit
		return dp[-1]


class Solution:

	def maxProfit(self, k, N, prices):
		if k == 0:
			return 0
		dp = [[1000, 0] for _ in range(k + 1)]
		for price in prices:
			for i in range(1, k + 1):
				dp[i][0] = min(dp[i][0], price - dp[i - 1][1])
				dp[i][1] = max(dp[i][1], price - dp[i][0])
		return dp[k][1]


class Solution:

	def maxProfit(self, K, N, arr):
		dp = [[0 for j in range(N)] for i in range(K + 1)]
		for i in range(1, K + 1):
			max_diff = -arr[0]
			for j in range(1, N):
				dp[i][j] = max(dp[i][j - 1], max_diff + arr[j])
				max_diff = max(max_diff, dp[i - 1][j] - arr[j])
		return dp[K][N - 1]


class Solution:

	def maxProfit(self, K, N, A):
		dp = [[[0 for i in range(K + 1)] for j in range(2)] for k in range(N + 1)]
		for i in range(N - 1, -1, -1):
			for buy in range(2):
				for count in range(1, K + 1):
					if buy == 1:
						profit = max(0 + dp[i + 1][1][count], -A[i] + dp[i + 1][0][count])
					else:
						profit = max(0 + dp[i + 1][0][count], A[i] + dp[i + 1][1][count - 1])
					dp[i][buy][count] = profit
		return dp[0][1][K]


class Solution:

	def maxProfit(self, k, n, price):
		dp = [[[0] * (k + 1) for i in range(2)] for j in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for buy in range(2):
				for limit in range(1, k + 1, 1):
					if buy == 1:
						by = -1 * price[i] + dp[i + 1][0][limit]
						skip = dp[i + 1][buy][limit]
						profit = max(by, skip)
					else:
						sell = price[i] + dp[i + 1][1][limit - 1]
						skip = dp[i + 1][buy][limit]
						profit = max(sell, skip)
					dp[i][buy][limit] = profit
		return dp[0][1][k]


class Solution:

	def maxProfit(self, k, N, prices):
		n = len(prices)
		dp = {}

		def f(i, buy, cap):
			if (i, buy, cap) in dp:
				return dp[i, buy, cap]
			if cap == 0:
				dp[i, buy, cap] = 0
				return 0
			if i == n:
				dp[i, buy, cap] = 0
				return 0
			if buy:
				dp[i, buy, cap] = max(-prices[i] + f(i + 1, 0, cap), 0 + f(i + 1, 1, cap))
			else:
				dp[i, buy, cap] = max(prices[i] + f(i + 1, 1, cap - 1), 0 + f(i + 1, 0, cap))
			return dp[i, buy, cap]
		return f(0, 1, k)


class Solution:

	def maxProfit(self, K, N, A):
		buy = [-9999 for i in range(N)]
		sell = [0 for i in range(N)]
		for p in A:
			buy[0] = max(buy[0], -p)
			sell[0] = max(sell[0], buy[0] + p)
			for k in range(1, K):
				if k < N:
					buy[k] = max(buy[k], sell[k - 1] - p)
					sell[k] = max(sell[k], buy[k] + p)
		if K > N:
			return sell[N - 1]
		else:
			return sell[K - 1]


class Solution:

	def maxProfit(self, K, N, A):
		prices = A
		alloc_arr = [[0 for col in range(N)] for row in range(K + 1)]
		for trans in range(1, K + 1):
			largest_difference = -float('inf')
			for day in range(1, N):
				transaction_day_ahead = alloc_arr[trans - 1][day - 1] - prices[day - 1]
				largest_difference = max(largest_difference, transaction_day_ahead)
				prev_day_val = alloc_arr[trans][day - 1]
				update_val = max(prev_day_val, prices[day] + largest_difference)
				alloc_arr[trans][day] = update_val
		return alloc_arr[K][N - 1]


class Solution:

	def maxProfit(self, K, N, A):
		profit = [[0 for i in range(N + 1)] for j in range(K + 1)]
		for i in range(1, K + 1):
			min_ = -9999
			for j in range(1, N):
				min_ = max(min_, profit[i - 1][j - 1] - A[j - 1])
				profit[i][j] = max(profit[i][j - 1], A[j] + min_)
		return profit[K][N - 1]


class Solution:

	def maxProfit(self, K, N, A):
		dp = [[[-1 for i in range(K + 1)] for i in range(2)] for i in range(N)]

		def f(ind, buy, cap, dp):
			if cap == 0:
				return 0
			if ind == N:
				return 0
			if dp[ind][buy][cap] != -1:
				return dp[ind][buy][cap]
			if buy:
				profit = max(-A[ind] + f(ind + 1, 0, cap, dp), 0 + f(ind + 1, 1, cap, dp))
			else:
				profit = max(A[ind] + f(ind + 1, 1, cap - 1, dp), 0 + f(ind + 1, 0, cap, dp))
			dp[ind][buy][cap] = profit
			return dp[ind][buy][cap]
		return f(0, 1, K, dp)


class Solution:

	def maxProfit(self, K, N, A):
		dp = [0] * N
		for tns in range(K):
			pos = -A[0]
			profit = 0
			for i in range(1, N):
				pos = max(pos, dp[i] - A[i])
				profit = max(profit, pos + A[i])
				dp[i] = profit
		return dp[-1]


class Solution:

	def maxProfit(self, K, N, A):
		hmap = {}

		def buy_and_sell(arr, i, j, b, n, k):
			if i == n or j == k:
				return 0
			if (i, j, b) not in hmap:
				if b == 0:
					ans = max(-arr[i] + buy_and_sell(arr, i + 1, j, 1, n, k), buy_and_sell(arr, i + 1, j, 0, n, k))
				else:
					ans = max(arr[i] + buy_and_sell(arr, i + 1, j + 1, 0, n, k), buy_and_sell(arr, i + 1, j, 1, n, k))
				hmap[i, j, b] = ans
			return hmap[i, j, b]
		return buy_and_sell(A, 0, 0, 0, N, K)


class Solution:

	def maxProfit(self, K, N, A):
		n = len(A)
		dp = {}

		def dfs(i, buying, k):
			if i == len(A) or k > K:
				return 0
			if (i, buying, k) in dp:
				return dp[i, buying, k]
			cool = dfs(i + 1, buying, k)
			if buying:
				total = dfs(i + 1, not buying, k) - A[i]
			else:
				total = dfs(i + 1, not buying, k + 1) + A[i]
			dp[i, buying, k] = max(total, cool)
			return dp[i, buying, k]
		return dfs(0, True, 1)
		dp = {}

		def dfs(i, buying, k):
			if i >= N or k > K:
				return 0
			if (i, buying, k) in dp:
				return dp[i, buying, k]
			cool = dfs(i + 1, buying, k)
			if buying:
				buy = dfs(i + 1, not buying, k) - A[i]
				dp[i, buying, k] = max(buy, cool)
			else:
				sell = dfs(i + 1, not buying, k + 1) + A[i]
				dp[i, buying, k] = max(sell, cool)
			return dp[i, buying, k]
		return dfs(0, True, 1)


class Solution:

	def maxProfit(self, K, N, A):
		profit = [[0 for i in range(N + 2)] for i in range(K + 2)]
		for i in range(K + 1):
			profit[i][0] = 0
		for j in range(N + 1):
			profit[0][j] = 0
		INT_MIN = -1 * (1 << 32)
		for i in range(1, K + 1):
			prevDiff = INT_MIN
			for j in range(1, N):
				prevDiff = max(prevDiff, profit[i - 1][j - 1] - A[j - 1])
				profit[i][j] = max(profit[i][j - 1], A[j] + prevDiff)
		return profit[K][N - 1]


class Solution:

	def maxProfit(self, k, n, prices):
		after = [[0 for x in range(k + 1)] for j in range(2)]
		for ind in range(n - 1, -1, -1):
			curr = [[0 for x in range(k + 1)] for j in range(2)]
			for count in range(1, k + 1):
				curr[1][count] = max(-prices[ind] + after[0][count], after[1][count])
				curr[0][count] = max(prices[ind] + after[1][count - 1], after[0][count])
			after = curr
		return after[1][k]


class Solution:

	def maxProfit(self, k, n, price):

		def manu(price, i, buy, count, dp):
			if count == 0:
				return 0
			if i == n:
				return 0
			if dp[i][buy][count] != -1:
				return dp[i][buy][count]
			if buy == 0:
				dp[i][buy][count] = max(manu(price, i + 1, 1, count - 1, dp) - price[i], manu(price, i + 1, 0, count, dp))
			else:
				dp[i][buy][count] = max(price[i] + manu(price, i + 1, 0, count - 1, dp), manu(price, i + 1, 1, count, dp))
			return dp[i][buy][count]
		dp = [[[-1 for i in range(2 * k + 1)] for i in range(2)] for i in range(n)]
		return manu(price, 0, 0, 2 * k, dp)


class Solution:

	def maxProfit(self, k, n, arr):
		dp = [[[0 for i in range(k + 1)] for j in range(2)] for _ in range(n + 1)]
		for i in range(2):
			for j in range(k + 1):
				dp[n][i][j] = 0
		for i in range(n + 1):
			for j in range(2):
				dp[i][j][0] = 0
		for idx in range(n - 1, -1, -1):
			for buy in range(2):
				for k in range(1, k + 1):
					profit = 0
					if buy:
						p = -arr[idx] + dp[idx + 1][0][k]
						np = 0 + dp[idx + 1][1][k]
						profit = max(profit, max(p, np))
					else:
						s = arr[idx] + dp[idx + 1][1][k - 1]
						ns = 0 + dp[idx + 1][0][k]
						profit = max(profit, max(s, ns))
					dp[idx][buy][k] = profit
		return dp[0][1][k]


class Solution:

	def maxProfit(self, K, N, A):
		dp = [[0 for i in range(len(A))] for j in range(K + 1)]
		for i in range(1, K + 1):
			res = float('-inf')
			for j in range(1, len(A)):
				res = max(res, dp[i - 1][j - 1] - A[j - 1])
				dp[i][j] = max(dp[i][j - 1], res + A[j])
		return dp[-1][-1]


class Solution:

	def solve(self, n, prices, k, buy, idx, dp):
		if idx == n or k == 0:
			return 0
		if dp[idx][buy][k] != -1:
			return dp[idx][buy][k]
		profit = 0
		if buy:
			inc = -prices[idx] + self.solve(n, prices, k, 0, idx + 1, dp)
			exc = self.solve(n, prices, k, 1, idx + 1, dp)
			profit = max(inc, exc)
		else:
			inc = prices[idx] + self.solve(n, prices, k - 1, 1, idx + 1, dp)
			exc = self.solve(n, prices, k, 0, idx + 1, dp)
			profit = max(inc, exc)
		dp[idx][buy][k] = profit
		return profit

	def maxProfit(self, K, N, A):
		buy = 1
		dp = [[[-1 for _ in range(K + 1)] for _ in range(2)] for _ in range(N)]
		return self.solve(N, A, K, buy, 0, dp)


class Solution:

	def maxProfit(self, k, n, price):
		dp = [[[0 for i in range(k + 1)] for j in range(2)] for l in range(n)]
		for i in range(n - 1, -1, -1):
			for j in range(k + 1):
				if i == n - 1:
					dp[i][0][j] = 0
					dp[i][1][j] = price[i] if j >= 1 else 0
				else:
					dp[i][0][j] = max(-price[i] + dp[i + 1][1][j], dp[i + 1][0][j])
					dp[i][1][j] = max(price[i] + dp[i + 1][0][j - 1] if j >= 1 else 0, dp[i + 1][1][j])
		return dp[0][0][k]


class Solution:

	def maxProfit(self, K, N, A):
		profit = [[0 for i in range(N + 1)] for j in range(K + 1)]
		for i in range(1, K + 1):
			prev_diff = float('-inf')
			for j in range(1, N):
				prev_diff = max(prev_diff, profit[i - 1][j - 1] - A[j - 1])
				profit[i][j] = max(profit[i][j - 1], A[j] + prev_diff)
		return profit[K][N - 1]


class Solution:

	def maxProfit(self, K, N, A):

		def solve(A, N, k, i, b, memo={}):
			if (k, i, b) in memo:
				return memo[k, i, b]
			if k == 0:
				return 0
			if i == N:
				return 0
			if b == 0:
				res = max(-A[i] + solve(A, N, k, i + 1, 1), solve(A, N, k, i + 1, 0))
				memo[k, i, b] = res
				return memo[k, i, b]
			else:
				res = max(A[i] + solve(A, N, k - 1, i + 1, 0), solve(A, N, k, i + 1, 1))
				memo[k, i, b] = res
				return memo[k, i, b]
		return solve(A, N, K, 0, 0)


class Solution:

	def maxProfit(self, K, N, A):
		dp = [[0 for i in range(N)] for _ in range(K + 1)]
		for eachk in range(1, K + 1):
			maxi = dp[eachk - 1][0] - A[0]
			for i in range(1, N):
				dp[eachk][i] = max(dp[eachk][i - 1], A[i] + maxi)
				maxi = max(maxi, dp[eachk - 1][i] - A[i])
		return dp[K][N - 1]


class Solution:

	def maxProfit(self, K, N, A):
		if K == 0 or N == 0:
			return 0
		if K >= N / 2:
			return sum((max(A[i + 1] - A[i], 0) for i in range(N - 1)))
		dp = [[0 for _ in range(N)] for _ in range(K + 1)]
		for i in range(1, K + 1):
			max_diff = -A[0]
			for j in range(1, N):
				dp[i][j] = max(dp[i][j - 1], A[j] + max_diff)
				max_diff = max(max_diff, dp[i - 1][j] - A[j])
		return dp[K][N - 1]


class Solution:

	def maxProfit(self, k, N, prices):
		minb = [float('inf')] * k
		maxs = [0] * k
		for j in range(len(prices)):
			for i in range(k):
				if i != 0:
					minb[i] = min(minb[i], prices[j] - maxs[i - 1])
				else:
					minb[i] = min(minb[i], prices[j])
				maxs[i] = max(maxs[i], prices[j] - minb[i])
		return maxs[k - 1]


class Solution:

	def maxProfit(self, K, N, price):
		dp = [[[0 for i in range(K + 1)] for i in range(2)] for i in range(N + 1)]
		for i in range(N - 1, -1, -1):
			for buy in range(2):
				for j in range(1, K + 1):
					if buy == 1:
						dp[i][buy][j] = max(-price[i] + dp[i + 1][0][j], 0 + dp[i + 1][1][j])
					else:
						dp[i][buy][j] = max(price[i] + dp[i + 1][1][j - 1], 0 + dp[i + 1][0][j])
		return dp[0][1][K]


class Solution:

	def maxProfit(self, K, N, A):
		dp = [[0 for i in range(N)] for j in range(K + 1)]
		for i in range(1, K + 1):
			mx_diff = -A[0]
			for j in range(1, N):
				dp[i][j] = max(dp[i][j - 1], A[j] + mx_diff)
				mx_diff = max(mx_diff, dp[i - 1][j] - A[j])
		return dp[-1][-1]


class Solution:

	def maxProfit(self, c, N, A):
		t = [[[0] * (c + 1) for i in range(2)] for j in range(N + 1)]
		for i in range(N - 1, -1, -1):
			for j in range(2):
				for k in range(1, c + 1):
					if j == 0:
						t[i][j][k] = max(t[i + 1][1][k] - A[i], t[i + 1][j][k])
					else:
						t[i][j][k] = max(t[i + 1][0][k - 1] + A[i], t[i + 1][j][k])
		return t[0][0][c]


class Solution:

	def solve(self, ind, op, arr, dp):
		if ind == len(arr):
			return 0
		if op == 0:
			return 0
		if dp[ind][op] != -1:
			return dp[ind][op]
		if op % 2 == 0:
			pick = -arr[ind] + self.solve(ind + 1, op - 1, arr, dp)
			skip = self.solve(ind + 1, op, arr, dp)
			profit = max(pick, skip)
		else:
			shel = arr[ind] + self.solve(ind + 1, op - 1, arr, dp)
			skipsell = self.solve(ind + 1, op, arr, dp)
			profit = max(shel, skipsell)
		dp[ind][op] = profit
		return dp[ind][op]

	def maxProfit(self, K, N, A):
		op = 2 * K
		ind = 0
		dp = [[-1 for i in range(op + 1)] for j in range(N + 1)]
		return self.solve(ind, op, A, dp)


class Solution:

	def maxProfit(self, k, n, prices):
		dp = [[[0 for i in range(k + 1)] for i in range(2)] for i in range(n + 1)]
		for i in range(n - 1, -1, -1):
			for buy in range(2):
				for cap in range(1, k + 1):
					if buy == 1:
						dp[i][buy][cap] = max(-prices[i] + dp[i + 1][0][cap], 0 + dp[i + 1][1][cap])
					else:
						dp[i][buy][cap] = max(prices[i] + dp[i + 1][1][cap - 1], 0 + dp[i + 1][0][cap])
		return dp[0][1][k]


class Solution:

	def maxProfit(self, k, N, prices):
		n = len(prices)
		after = [[0] * (k + 1) for i in range(2)]
		curr = [[0] * (k + 1) for i in range(2)]
		for idx in range(n - 1, -1, -1):
			for buy in range(0, 2):
				for cap in range(1, k + 1):
					profit = 0
					if buy:
						profit = max(-prices[idx] + after[0][cap], 0 + after[1][cap])
					else:
						profit = max(prices[idx] + after[1][cap - 1], 0 + after[0][cap])
					curr[buy][cap] = profit
			after = curr
		return after[1][k]


class Solution:

	def maxProfit(self, k, N, A):
		prev = [0] * N
		for i in range(k):
			dp = [0] * N
			maxDiff = -A[0]
			for j in range(1, N):
				dp[j] = max(dp[j - 1], A[j] + maxDiff)
				maxDiff = max(maxDiff, prev[j] - A[j])
			prev = dp
		return prev[-1]


class Solution:

	def maxProfit(self, k, n, prices):
		n = len(prices)
		dp = [[[0 for i in range(k + 1)] for j in range(2)] for p in range(n + 1)]
		for ind in range(n - 1, -1, -1):
			for buy in range(2):
				for cap in range(1, k + 1):
					if buy == 1:
						dp[ind][buy][cap] = max(-prices[ind] + dp[ind + 1][0][cap], 0 + dp[ind + 1][1][cap])
					else:
						dp[ind][buy][cap] = max(prices[ind] + dp[ind + 1][1][cap - 1], 0 + dp[ind + 1][0][cap])
		return dp[0][1][k]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maxProfit(self, K, n, price):
		next = [[0] * (K + 1) for _ in range(2)]
		for i in range(n - 1, -1, -1):
			curr = [[0] * (K + 1) for _ in range(2)]
			for buy in range(2):
				for cap in range(1, K + 1):
					if buy:
						Buy = next[0][cap] - price[i]
						notBuy = next[1][cap]
						profit = max(Buy, notBuy)
					else:
						sell = next[1][cap - 1] + price[i]
						notSell = next[0][cap]
						profit = max(sell, notSell)
					curr[buy][cap] = profit
			next = curr
		return curr[1][K]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def maxProfit(self, K, n, price):

		def f(i, buy, cap):
			if i == n or cap == 0:
				return 0
			if dp[i][buy][cap] != -1:
				return dp[i][buy][cap]
			if buy:
				Buy = f(i + 1, 0, cap) - price[i]
				notBuy = f(i + 1, 1, cap)
				profit = max(Buy, notBuy)
			else:
				sell = f(i + 1, 1, cap - 1) + price[i]
				notSell = f(i + 1, 0, cap)
				profit = max(sell, notSell)
			dp[i][buy][cap] = profit
			return dp[i][buy][cap]
		dp = [[[-1] * (K + 1) for _ in range(2)] for __ in range(n)]
		return f(0, 1, K)


class Solution:

	def maxProfit(self, K, N, arr):
		nextrow = [[0 for k in range(K + 1)] for j in range(0, 2)]
		for i in range(N - 1, -1, -1):
			curr = [[0 for k in range(K + 1)] for j in range(0, 2)]
			for bought in range(0, 2):
				for maxAllowed in range(1, K + 1):
					profit = 0
					if bought == 0:
						buy = -arr[i] + nextrow[1][maxAllowed]
						notbuy = nextrow[0][maxAllowed]
						profit = max(buy, notbuy)
					else:
						sell = arr[i] + nextrow[0][maxAllowed - 1]
						notsell = nextrow[1][maxAllowed]
						profit = max(sell, notsell)
					curr[bought][maxAllowed] = profit
			nextrow = curr
		return nextrow[0][K]


class Solution:

	def maxProfit(self, k, n, A):
		dp = [[[0 for _ in range(k + 1)] for _ in range(2)] for _ in range(n + 1)]
		for ind in range(0, n):
			for buy in range(2):
				dp[ind][buy][0] = 0
		for buy in range(2):
			for atMost in range(k + 1):
				dp[n][buy][atMost] = 0
		for ind in range(n - 1, -1, -1):
			for buy in range(2):
				for atMost in range(1, k + 1):
					if buy:
						take = -A[ind] + dp[ind + 1][0][atMost]
						noTake = 0 + dp[ind + 1][1][atMost]
						dp[ind][buy][atMost] = max(take, noTake)
					else:
						take = A[ind] + dp[ind + 1][1][atMost - 1]
						noTake = 0 + dp[ind + 1][0][atMost]
						dp[ind][buy][atMost] = max(take, noTake)
		return dp[0][1][k]


class Solution:

	def maxProfit(self, K, N, arr):

		def solve(i, bought, maxAllowed):
			if i == N or maxAllowed == 0:
				return 0
			if dp[i][bought][maxAllowed] != -1:
				return dp[i][bought][maxAllowed]
			profit = 0
			if bought == 0:
				buy = -arr[i] + solve(i + 1, 1, maxAllowed)
				notbuy = solve(i + 1, 0, maxAllowed)
				profit = max(buy, notbuy)
			elif bought == 1:
				sell = arr[i] + solve(i + 1, 0, maxAllowed - 1)
				notsell = solve(i + 1, 1, maxAllowed)
				profit = max(sell, notsell)
			dp[i][bought][maxAllowed] = profit
			return dp[i][bought][maxAllowed]
		dp = [[[-1 for k in range(K + 1)] for j in range(0, 2)] for i in range(N)]
		return solve(0, False, K)


class Solution:

	def maxProfit(self, k, n, prices):
		after = [0] * (2 * k + 1)
		cur = [0] * (2 * k + 1)
		for ind in range(n - 1, -1, -1):
			for tansNo in range(2 * k - 1, -1, -1):
				if tansNo % 2 == 0:
					profit = max(-1 * prices[ind] + after[tansNo + 1], after[tansNo])
				else:
					profit = max(prices[ind] + after[tansNo + 1], after[tansNo])
				cur[tansNo] = profit
			after = list(cur)
		return after[0]


class Solution:

	def maxProfit(self, k, n, prices):
		dp = [[0] * (2 * k + 1) for i in range(n + 1)]
		for ind in range(n - 1, -1, -1):
			for tansNo in range(2 * k - 1, -1, -1):
				if tansNo % 2 == 0:
					profit = max(-1 * prices[ind] + dp[ind + 1][tansNo + 1], dp[ind + 1][tansNo])
				else:
					profit = max(prices[ind] + dp[ind + 1][tansNo + 1], dp[ind + 1][tansNo])
				dp[ind][tansNo] = profit
		return dp[0][0]


class Solution:

	def maxProfit(self, K, N, A):
		after = [[0] * (K + 1) for i in range(2)]
		cur = [[0] * (K + 1) for i in range(2)]
		for ind in range(N - 1, -1, -1):
			for buy in range(2):
				for cap in range(1, K + 1):
					if buy:
						profit = max(-1 * A[ind] + after[0][cap], after[1][cap])
					else:
						profit = max(A[ind] + after[1][cap - 1], after[0][cap])
					cur[buy][cap] = profit
			after = list(cur)
		return after[1][K]


def solver(arr, buySell, cap, index, dct):
	if index == len(arr) or cap == 0:
		return 0
	if (buySell, cap, index) in dct:
		return dct[buySell, cap, index]
	res = 0
	if buySell:
		res = max(-arr[index] + solver(arr, 0, cap, index + 1, dct), 0 + solver(arr, 1, cap, index + 1, dct))
	else:
		res = max(arr[index] + solver(arr, 1, cap - 1, index + 1, dct), 0 + solver(arr, 0, cap, index + 1, dct))
	dct[buySell, cap, index] = res
	return res

class Solution:

	def maxProfit(self, K, N, A):
		dct = dict()
		return solver(A, 1, K, 0, dct)


class Solution:

	def maxProfit(self, k, n, price):
		profit = [[0 for i in range(n + 1)] for j in range(k + 1)]
		for i in range(1, k + 1):
			prevDiff = float('-inf')
			for j in range(1, n):
				prevDiff = max(prevDiff, profit[i - 1][j - 1] - price[j - 1])
				profit[i][j] = max(profit[i][j - 1], price[j] + prevDiff)
		return profit[k][n - 1]


class Solution:

	def maxProfit(self, K, N, A):
		dp = [[-1 for i in range(2 * K + 1)] for j in range(N)]
		return f(2 * K, N - 1, A, dp)

def f(trans, n, A, dp):
	if trans == 0:
		dp[n][trans] = 0
		return 0
	if n == 0:
		if trans % 2 != 0:
			dp[n][trans] = -1 * A[0]
			return -1 * A[0]
		else:
			dp[n][trans] = 0
			return 0
	if dp[n][trans] != -1:
		return dp[n][trans]
	if trans % 2 == 0:
		dp[n][trans] = max(A[n] + f(trans - 1, n - 1, A, dp), f(trans, n - 1, A, dp))
		return dp[n][trans]
	else:
		dp[n][trans] = max(A[n] * -1 + f(trans - 1, n - 1, A, dp), f(trans, n - 1, A, dp))
		return dp[n][trans]


class Solution:

	def maxProfit(self, k, n, prices):
		n = len(prices)
		front = [[0 for x in range(k + 1)] for x in range(2)]
		curr = [[0 for x in range(k + 1)] for x in range(2)]
		for i in range(n - 1, -1, -1):
			for buy in range(2):
				for k1 in range(k - 1, -1, -1):
					if buy:
						t1 = -prices[i] + front[0][k1]
						t2 = 0 + front[1][k1]
					else:
						t1 = prices[i] + front[1][k1 + 1]
						t2 = 0 + front[0][k1]
					curr[buy][k1] = max(t1, t2)
			front = curr.copy()
		return front[1][0]


class Solution:
	dp = [[[]]]

	def util(self, prices, n, idx, buy, capacity):
		if self.dp[idx][buy][capacity] != -1:
			return self.dp[idx][buy][capacity]
		if idx == n or capacity == 0:
			return 0
		profit = 0
		if buy:
			buy_it = -prices[idx] + self.util(prices, n, idx + 1, 0, capacity)
			dont_buy_it = self.util(prices, n, idx + 1, 1, capacity)
			profit = max(buy_it, dont_buy_it)
		else:
			sell_it = prices[idx] + self.util(prices, n, idx + 1, 1, capacity - 1)
			dont_sell_it = self.util(prices, n, idx + 1, 0, capacity)
			profit = max(sell_it, dont_sell_it)
		self.dp[idx][buy][capacity] = profit
		return self.dp[idx][buy][capacity]

	def maxProfit(self, K, N, A):
		dp = [[[0 for _ in range(K + 1)] for _ in range(2)] for _ in range(N + 1)]
		for i in range(N - 1, -1, -1):
			for buy in range(2):
				for cap in range(1, K + 1):
					profit = 0
					if buy:
						buy_it = -A[i] + dp[i + 1][0][cap]
						dont_buy_it = dp[i + 1][1][cap]
						profit = max(buy_it, dont_buy_it)
					else:
						sell_it = A[i] + dp[i + 1][1][cap - 1]
						dont_sell_it = dp[i + 1][0][cap]
						profit = max(sell_it, dont_sell_it)
					dp[i][buy][cap] = profit
		return dp[0][1][K]


class Solution:

	def maxProfit(self, k, n, arr):
		if n == 0 or n == 1:
			return 0
		dp = [0] * n
		for i in range(k):
			pos = -arr[0]
			profit = 0
			for j in range(1, n):
				pos = max(pos, dp[j] - arr[j])
				profit = max(profit, pos + arr[j])
				dp[j] = profit
		return dp[-1]


class Solution:

	def maxProfit(self, K, N, A):
		dp = [[0] * (N + 1) for i in range(K + 1)]
		for z in range(1, K + 1):
			maxdiff = dp[z - 1][0] - A[0]
			for i in range(2, N + 1):
				dp[z][i] = max(dp[z][i], dp[z - 1][i])
				dp[z][i] = max(dp[z][i], dp[z][i - 1])
				dp[z][i] = max(dp[z][i], maxdiff + A[i - 1])
				maxdiff = max(maxdiff, dp[z - 1][i - 1] - A[i - 1])
		return dp[K][N]


class Solution:

	def maxProfit(self, K, N, A):
		dp = [0] * (N + 1)
		for t in range(K):
			curr = -A[0]
			profit = 0
			for i in range(1, N):
				curr = max(curr, dp[i] - A[i])
				profit = max(profit, curr + A[i])
				dp[i] = profit
		return dp[N - 1]


class Solution:

	def maxProfit(self, k, N, prices):
		dp = [[[0 for _ in range(K + 1)] for _ in range(3)] for _ in range(len(prices) + 1)]
		return self.tab(prices, N, dp, k)

	def tab(self, prices, n, dp, trans):
		for current in range(n - 1, -1, -1):
			for buy in range(2):
				for transaction in range(1, trans + 1):
					if buy:
						dp[current][buy][transaction] = max(-prices[current] + dp[current + 1][False][transaction], dp[current + 1][True][transaction])
					else:
						dp[current][buy][transaction] = max(prices[current] + dp[current + 1][True][transaction - 1], dp[current + 1][False][transaction])
		return dp[0][1][trans]

	def solve(self, prices, current, canBuy, transaction, dp):
		profit = 0
		if current == len(prices) or transaction == 0:
			return 0
		if dp[current][canBuy][transaction] != -1:
			return dp[current][canBuy][transaction]
		if canBuy:
			profit = max(-prices[current] + self.solve(prices, current + 1, False, transaction, dp), self.solve(prices, current + 1, True, transaction, dp))
		else:
			profit = max(prices[current] + self.solve(prices, current + 1, True, transaction - 1, dp), self.solve(prices, current + 1, False, transaction, dp))
		dp[current][canBuy][transaction] = profit
		return profit