Maximum Profit (IV)

The goal is to make maximum profit given one stock values with a limited number of transactions

The idea is:

1) Create a 2 dimension list with the first dimension being the number of possible transaction and the second dimension being the number of stock values. Initialize everything to 0

2) Iterate over the number of transaction, call the current transaction the i-th transaction

3) Iterate over the days (the stock values), call this day the j-th day

4) Compute the direct performance between today and yesterday (j and j-1)

5) At this time we need to choose the best option among:

a. A i-th position is already open, continue the position: add the performance to the yesterday total profit for i positions

b. No i-th position is open, we can open this new position: add the performance to the yesterday total profit for i-1 positions

c. No i-th position is open but we do not open one: take the yesterday total profit for i-1 positions

5') We can't decide to close a position during the processing of this day otherwise it won't be possible at the next day to know if the position has been closed and if we can or can't add the performance without using a new position

6) At the end of the loop on the day we can check where it was best to close the position: for this we define the best profit for day j as the max between profit of this day vs profit of yesterday

7) best profit is hence the profit on last day using our total number of possible transactions

def maxProfit(k: int, prices: List[int]) -> int:
    if k==0 or len(prices) <= 1:
        return(0)

    dp = [[0 for _ in range(len(prices))] for _ in range(k+1)]
    for i in range(1, k+1):
        for j in range(1, len(prices)):
            profit = prices[j] - prices[j-1] # profit vs yesterday

            # once a transaction i is open we need to keep it until the end
            # best profit for i transactions at day j is max between
            # 1) best profit for i transactions at day j-1 + today profit (position i is already open)
            # 2) best profit for i-1 transactions at day j-1 + today profit (position i has been open yesterday)
            # 3) best profit for i-1 transactions at day j-1 (position i is still close)
            # best profit for i transactions at day j-1 (dp[i][j-1]) is not in the max otherwise it would allow to open and close multiple positions
            dp[i][j] = max(dp[i][j-1] + profit, dp[i-1][j-1] + profit, dp[i-1][j-1])
        # at the end we take the best profit for today as the max between best profit between today and yesterday. It reprensents if it is best to close position yesterday or keep it until today. Once again this should be done outside the first loop otherwise it would allow to close and reopen multiple position
        for j in range(1, len(prices)):
            dp[i][j] = max(dp[i][j], dp[i][j-1])

    return(dp[-1][-1])