Best Time Buy/Sell Stock IV — At Most k Transactions

Problem

At most k buy-sell transactions. Maximize profit.

Approach — State Machine with k Transactions

For each transaction, track buy/sell states. If k >= n//2, equivalent to unlimited transactions.

Time: O(k*n) | Space: O(k)

Solutions

Python

class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        n=len(prices)
        if k>=n//2:
            return sum(max(0,prices[i]-prices[i-1]) for i in range(1,n))
        buy=[-float('inf')]*k; sell=[0]*k
        for p in prices:
            for t in range(k):
                buy[t]=max(buy[t],(sell[t-1] if t>0 else 0)-p)
                sell[t]=max(sell[t],buy[t]+p)
        return sell[-1] if k>0 else 0

C++

class Solution {
public:
    int maxProfit(int k, vector<int>& prices){
        int n=prices.size();
        if(k>=n/2){int r=0;for(int i=1;i<n;i++)r+=max(0,prices[i]-prices[i-1]);return r;}
        vector<int> buy(k,INT_MIN),sell(k,0);
        for(int p:prices) for(int t=0;t<k;t++){
            buy[t]=max(buy[t],(t>0?sell[t-1]:0)-p);
            sell[t]=max(sell[t],buy[t]+p);
        }
        return sell[k-1];
    }
};

Complexity

Time: O(k*n) | Space: O(k)