Hard

Best Time to Buy and Sell Stock IV

LAB

Return the maximum profit from at most k buy-sell transactions, holding at most one share at a time.

EXAMPLES

Example 1

Input
{
  "k": 2,
  "prices": [
    2,
    4,
    1
  ]
}

Output
2

FUNCTION SHAPE

k: intprices: intArray→int

SOLUTION NOTE

Add transaction count to state. Decrement k when completing a sell (a full transaction).

Reveal reference solution +

pythonREFERENCE

def maxProfit(self, k: int, prices: List[int]) -> int:
    @cache
    def dp(i, k, holding):
        if i >= len(prices) or k == 0: return 0
        if holding:
            return max(prices[i] + dp(i+1, k-1, False), dp(i+1, k, True))
        else:
            return max(-prices[i] + dp(i+1, k, True), dp(i+1, k, False))

    return dp(0, k, False)

TimeO(n × k)

SpaceO(n × k)

Open on LeetCode ↗