from typing import *


class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        neg_infinity, N = -1e7, len(prices)

        if k > N // 2:
            dp = [[0, 0] for _ in range(N)]
            dp[0][0], dp[0][1] = 0, -prices[0]
            for i in range(1, N):
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
            return dp[-1][0]

        dp = [[[0, 0] for _ in range(k+1)] for _ in range(N)]
        for i in range(1, k+1):
            dp[0][i][0], dp[0][i][1] = 0, -prices[0]
        for i in range(N):
            dp[i][0][0], dp[i][0][1] = 0, neg_infinity

        for i in range(1, N):
            for j in range(1, k+1):
                dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i])
                dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i])
        return dp[-1][-1][0]


if __name__ =='__main__':
    s = Solution()
    print(s.maxProfit(2, [3,2,6,5,0,3]))
