'''
keys: DP
Solutions:
Similar:
T:
S:
'''
from typing import List

class Solution:
    # https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/54117/Clean-Java-DP-solution-with-comment
    # dp[i][j] = maximum profit from at most i transactions using prices[0..j]
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        # special case
        if not prices or k == 0:
            return 0
        if 2 * k > n: # do daily trade
            res = 0
            for i, j in zip(prices[:-1], prices[1:]):
                res += max(0, j - i)
            return res

        # general case
        dp = [ [0] * n for _ in range(k + 1) ]
        for i in range(1, k+1):
            # localMax is the current max profit
            localMax = dp[i-1][0] - prices[0] # or - prices[0]
            for j in range(1, n):
                # hold the stock: dp[i][j-1]; sell the stock: localMax + prices[j]
                dp[i][j] = max(dp[i][j-1], prices[j] + localMax)
                # localMax means the maximum profit of just doing at most i-1 
                # transactions, using at most first j-1 prices, and buying 
                # the stock at price[j]: this is used for the next loop.
                localMax =  max(localMax, dp[i - 1][j - 1] - prices[j])
        return dp[k][n - 1]

        
    # concise version, the method to go
    # https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/discuss/54117/Clean-Java-DP-solution-with-comment
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        # special case
        if not prices or k == 0:
            return 0
        if 2 * k > n: # do daily trade
            res = 0
            for i, j in zip(prices[:-1], prices[1:]):
                res += max(0, j - i)
            return res

        # general case
        dp = [ [0] * n for _ in range(k + 1) ]
        for i in range(1, k+1): # i == 0 or j == 0, dp will be 0, so dont need to check
            localMax = float("-inf")
            for j in range(1, n):
                # localMax is the max profit by selling prev stock
                localMax = max(localMax, dp[i-1][j-1] - prices[j-1]) 
                dp[i][j] = max(dp[i][j-1], localMax + prices[j]) # hold stock/ do transaction
        return dp[k][n-1]
        
    
    
    
    def maxProfit(self, k: int, prices: List[int]) -> int:
        '''
        The value of dp[i][j][l] represents the best profit we can have at the
        end of the i-th day, with j remaining transactions to make and l stocks.
        one transaction: 1 buy + 1 sell
        '''
        n = len(prices)
        # special case
        if not prices or k == 0:
            return 0
        if 2*k > n:
            res = 0
            for i, j in zip(prices[:-1], prices[1:]):
                res += max(0, j - i)
            return res
        # general case
        # dp[i][used_k][ishold] = balance
        # ishold: 0 nothold, 1 hold
        dp = [[[-float("inf")] for _ in range(k+1)] for _ in range(n)]
        
        # set starting value
        dp[0][0][0] = 0
        dp[0][1][1] = -prices[0]
        
        for i in range(1, n):
            for j in range(k+1):
                # transition: keep not holding or selling
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i])
                # keep holding or buying, but you need at least 1 transaction
                if j > 0:
                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
        res = max(dp[-1][j][0] for j in range(k+1))
        return res





