338. Maximum Profit With At Most K Transactions

Given an array of n daily stock prices and an integer k, find the maximum total profit obtainable from at most k buy-sell transactions, where a new buy can only happen after the previous sell (no overlapping transactions, and at most one share held at a time).

Input: Three lines: k (max transactions); n (number of days); n space-separated daily prices. Output: Print a single integer - the maximum total profit from at most k transactions.

1 <= n <= 1000, 0 <= k <= 100

Explicitly checking for the 'k is effectively unlimited' shortcut (k >= n/2) avoids allocating an oversized DP table when it's completely unnecessary - a practical optimization worth including for very large k values.

Find the maximum profit from at most k non-overlapping buy-sell transactions on a stock. Brute force: Try every possible combination of up to k buy-sell pairs directly - this is combinatorially expensive, when the running-maxdiff DP technique computes the optimal profit for all transaction counts efficiently. Optimised: Maintaining a running 'best net value if bought on some earlier day using one fewer transaction' (maxdiff) as you sweep days left-to-right avoids needing a fresh O(n) search for the best buy day at every single day - this turns what would be an O(n² * k) brute DP into an O(n*k) solution.

Recursively try every possible way to schedule up to k non-overlapping buy-sell transactions: at each day, either skip it, or (if not holding stock) buy, or (if holding) sell, branching over all choices and taking the maximum profit over all complete transaction sequences. Because the same (day, transactions-used, holding-state) situation is recomputed repeatedly along different recursion paths, this take exponential time in the worst case. It is correct because it exhaustively considers every legal transaction schedule. Time: O(2^n) Space: O(n) recursion depth

Keep the same dp[t][i] recurrence, but notice the inner maximum over j of (dp[t-1][j] - prices[j]) can be tracked incrementally: as i increases by 1, update a running variable maxDiff = max(maxDiff, dp[t-1][i-1] - prices[i-1]) once per (t,i) instead of re-scanning all previous j from scratch. Then dp[t][i] = max(dp[t][i-1], prices[i] + maxDiff). This collapses the O(n) inner search into O(1) amortized work per state, dropping the total time from O(n^2 k) to O(nk), which is essential since n and k can both reach into the hundreds/thousands. Time: O(nk) Space: O(nk) (reducible to O(n) with two rolling rows)

Define dp[t][i] = max profit using at most t transactions considering the first i days. For each transaction count t and day i, either don't transact on day i (dp[t][i-1]) or sell on day i after having bought on some earlier day j < i (prices[i] - prices[j] + dp[t-1][j]), and take the best over all valid j. Filling this table bottom-up with an explicit inner loop over all previous buy days j removes the exponential blowup of brute force and guarantees each (t, i) state is computed exactly once, at the cost of an extra O(n) search over j. Time: O(n^2 k) Space: O(nk)

1. dp[t][d] = maximum profit using at most t transactions, considering prices up to day d. 2. Track, while sweeping day d left to right for a fixed t, a running 'maxdiff' = max over earlier days e of (dp[t-1][e] - price[e]) - this turns the naive O(n) inner search for the best buy day into an O(1) running update. 3. If k is large enough that it's no real constraint (k >= n/2), the answer collapses to simply summing every positive day-to-day price increase (the unlimited-transactions case).

Time: O(n*k) with the maxdiff optimization; the unlimited-transactions shortcut (when k is large) runs in O(n). Space: O(n*k) for the full DP table (reducible to O(n) with careful row reuse, since each transaction count's row only depends on the previous one).

Test k = 0 (no transactions allowed, profit is 0), a strictly decreasing price array (profit is 0), and k large relative to n (k >= n/2, which per the hint collapses to the unlimited-transactions case).

Be ready to explain the maxdiff running-update trick clearly - it's the exact same kind of optimization used in the basic 'Best Time to Buy and Sell Stock' problem (tracking a running minimum), just generalized to track a running 'best net profit position' across transaction counts.