Maximum profit by buying and selling a share at most k times

Problem Statement

You are given an array prices[] where prices[i] is the price of a stock on day i, and an integer k. You can complete at most k transactions (each transaction = buy then sell). You must sell before buying again. Find the maximum profit.

Example:

• Input: prices = [2, 4, 1], k = 2

• Output: 2

• Explanation: Buy on day 1 (price=2), sell on day 2 (price=4). Profit = 2.

• Input: prices = [3, 2, 6, 5, 0, 3], k = 2

• Output: 7

• Explanation: Buy on day 2 (price=2), sell on day 3 (price=6), profit=4. Buy on day 5 (price=0), sell on day 6 (price=3), profit=3. Total = 7.

Noob-Friendly Explanation

You have a crystal ball that shows you future stock prices. You're allowed to buy and sell a stock at most k times. Each time you must buy first, then sell. You can't hold more than one stock at a time. What's the most money you can make?

Think of it like having k "trading cards" — each card lets you do one buy-sell pair. You want to use your cards on the best opportunities!

Approach 1: Brute Force (Recursion)

Intuition

At each day, decide: do nothing, buy (if not holding), or sell (if holding). Track how many transactions are left and whether we're holding a stock.

Algorithm

1. Use recursion with state: current day, transactions remaining, whether holding stock.
2. At each day, try all valid actions.
3. Return the maximum profit.

class Solution {
    public int maxProfit(int k, int[] prices) {
        return solve(prices, 0, k, false);
    }

    private int solve(int[] prices, int day, int transLeft, boolean holding) {
        if (day == prices.length || transLeft == 0) return 0;

        // Option 1: Do nothing
        int doNothing = solve(prices, day + 1, transLeft, holding);

        if (holding) {
            // Option 2: Sell
            int sell = prices[day] + solve(prices, day + 1, transLeft - 1, false);
            return Math.max(doNothing, sell);
        } else {
            // Option 2: Buy
            int buy = -prices[day] + solve(prices, day + 1, transLeft, true);
            return Math.max(doNothing, buy);
        }
    }
}

Complexity Analysis

• Time Complexity: O(n^(2k)) - Exponential branching at each step.
• Space Complexity: O(k) - Recursion stack depth proportional to transactions.

Approach 2: Optimal (Dynamic Programming)

Intuition

Use a 2D DP table where dp[t][d] = max profit using at most t transactions up to day d. For each transaction, we track the best day to buy so far.

Algorithm

1. If k >= n/2, we can do unlimited transactions — just sum all positive differences.
2. Otherwise, create dp[k+1][n].
3. For each transaction t and day d: dp[t][d] = max(dp[t][d-1], prices[d] + maxDiff) where maxDiff = max(maxDiff, dp[t-1][d] - prices[d]).

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n <= 1 || k == 0) return 0;

        // If k >= n/2, unlimited transactions
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }

        // dp[t][d] = max profit using at most t transactions up to day d
        int[][] dp = new int[k + 1][n];

        for (int t = 1; t <= k; t++) {
            // maxDiff tracks the best (dp[t-1][d] - prices[d]) seen so far
            int maxDiff = -prices[0];

            for (int d = 1; d < n; d++) {
                dp[t][d] = Math.max(dp[t][d - 1], prices[d] + maxDiff);
                maxDiff = Math.max(maxDiff, dp[t - 1][d] - prices[d]);
            }
        }

        return dp[k][n - 1];
    }
}

Complexity Analysis

• Time Complexity: O(n*k) - Two nested loops: k transactions and n days.
• Space Complexity: O(n*k) - 2D DP table.