19. Stock Buy and Sell – Max K Transactions Allowed

The problem can be found at the following link: Question Link

Problem Description

In the stock market, a person can buy a stock and sell it on a future date. You are given an array prices[] representing stock prices on different days and a positive integer k.

Find out the maximum profit a person can make with at most k transactions.

A transaction consists of buying and subsequently selling a stock. A new transaction can only start after completing the previous one.

Examples

Example 1:

Input:

prices = [10, 22, 5, 80]
k = 2

Output:

87

Explanation:

  1. Buy at 10, Sell at 22 β†’ Profit = 12

  2. Buy at 5, Sell at 80 β†’ Profit = 75 Total Profit = 12 + 75 = 87

Example 2:

Input:

prices = [20, 580, 420, 900]
k = 3

Output:

1040

Explanation:

  1. Buy at 20, Sell at 580 β†’ Profit = 560

  2. Buy at 420, Sell at 900 β†’ Profit = 480 Total Profit = 560 + 480 = 1040

Example 3:

Input:

prices = [100, 90, 80, 50, 25]
k = 1

Output:

0

Explanation:

  • The stock price is continuously decreasing, so there is no profit possible.

Constraints:

  • $(1 \leq \text{prices.size()} \leq 10^3)$

  • $(1 \leq k \leq 200)$

  • $(1 \leq \text{prices}[i] \leq 10^3)$

Optimized Dynamic Programming (1D DP, O(KΓ—N) Time, O(2K) Space)

Approach:

  1. If 2 * k >= n, it's optimal to perform all profitable transactions, similar to an unlimited transactions problem.

  2. Otherwise, we use a 1D DP table (dp[2*k+1]) to store the best profit for different transaction states:

    • Odd indices β†’ Buying states

    • Even indices β†’ Selling states

  3. Iterate through the stock prices and update dp[] based on previous values:

    • If buying, maximize profit by either holding or buying today.

    • If selling, maximize profit by either selling today or holding.

Algorithm Steps:

  1. If k == 0, return 0 (no transactions allowed).

  2. If 2 * k >= n, return the sum of all upward price differences.

  3. Initialize dp[2*k+1] with -∞ for buy states and 0 for the rest.

  4. Iterate through prices and update dp[j] for all transactions.

Time and Auxiliary Space Complexity

  • Expected Time Complexity: O(K Γ— N), since we iterate over prices[] for each transaction.

  • Expected Auxiliary Space Complexity: O(2K), since we only use a dp[] array of size 2K + 1.

Code (C++)

class Solution {
  public:
    int maxProfit(vector<int>& prices, int k) {
        int n = prices.size();
        if (n == 0 || k == 0) return 0;
        if (2 * k >= n) {
            int profit = 0;
            for (int i = 1; i < n; i++)
                profit += max(0, prices[i] - prices[i - 1]);
            return profit;
        }
        vector<int> dp(2 * k + 1, INT_MIN);
        dp[0] = 0;
        for (int price : prices)
            for (int j = 1; j <= 2 * k; j++)
                dp[j] = j % 2 ? max(dp[j], dp[j - 1] - price) : max(dp[j], dp[j - 1] + price);
        return dp[2 * k];
    }
};
⚑ Alternative Approaches

2️⃣ Dynamic Programming (O(KΓ—N) Time, O(KΓ—N) Space) β€” 2D DP

Algorithm Steps:

  1. Use a 2D DP table, where dp[i][j] represents the maximum profit at day j with at most i transactions.

  2. Base Case:

    • dp[0][j] = 0 (No transactions, no profit).

    • dp[i][0] = 0 (At day 0, profit is zero).

  3. Recurrence Relation: $[ dp[i][j] = \max(dp[i][j-1], prices[j] + \max(dp[i-1][p] - prices[p]) \quad \text{for } 0 \leq p < j ]$

    • dp[i][j-1]: No transaction on day j.

    • prices[j] + max(dp[i-1][p] - prices[p]): Buy at some p, sell at j.

class Solution {
  public:
    int maxProfit(vector<int>& prices, int k) {
        int n = prices.size();
        if (n == 0 || k == 0) return 0;
        vector<vector<int>> dp(k + 1, vector<int>(n, 0));
        for (int i = 1; i <= k; i++) {
            int maxDiff = -prices[0];
            for (int j = 1; j < n; j++) {
                dp[i][j] = max(dp[i][j - 1], prices[j] + maxDiff);
                maxDiff = max(maxDiff, dp[i - 1][j] - prices[j]);
            }
        }
        return dp[k][n - 1];
    }
};

βœ… Time Complexity: O(K Γ— N) βœ… Space Complexity: O(K Γ— N)

3️⃣ Recursive + Memoization (O(KΓ—N) Time, O(KΓ—N) Space)

Algorithm Steps:

  1. Define a recursive function solve(i, t, holding), where:

    • i is the current index (day).

    • t is the number of transactions left.

    • holding is true if we own a stock.

  2. Base Cases:

    • If i == n or t == 0, return 0.

  3. Recurrence Relation:

    • If holding:

      • Sell: prices[i] + solve(i + 1, t - 1, false).

      • Hold: solve(i + 1, t, true).

    • If not holding:

      • Buy: -prices[i] + solve(i + 1, t, true).

      • Skip: solve(i + 1, t, false).

  4. Use Memoization (dp[i][t][holding]) to store computed values.

class Solution {
  public:
    vector<vector<vector<int>>> dp;
    int solve(vector<int>& prices, int i, int t, bool holding) {
        if (i == prices.size() || t == 0) return 0;
        if (dp[i][t][holding] != -1) return dp[i][t][holding];
        int skip = solve(prices, i + 1, t, holding);
        if (holding)
            return dp[i][t][holding] = max(skip, prices[i] + solve(prices, i + 1, t - 1, false));
        else
            return dp[i][t][holding] = max(skip, -prices[i] + solve(prices, i + 1, t, true));
    }

    int maxProfit(vector<int>& prices, int k) {
        int n = prices.size();
        dp.assign(n, vector<vector<int>>(k + 1, vector<int>(2, -1)));
        return solve(prices, 0, k, false);
    }
};

βœ… Time Complexity: O(K Γ— N) βœ… Space Complexity: O(K Γ— N) (recursion stack)

Comparison of Approaches

Approach

⏱️ Time Complexity

πŸ—‚οΈ Space Complexity

βœ… Pros

⚠️ Cons

1D DP (Space Optimized)

🟑 O(K Γ— N)

🟒 O(2K)

Best space-efficient solution

Harder to understand

2D DP (Tabulation)

🟑 O(K Γ— N)

πŸ”΄ O(K Γ— N)

Intuitive approach

High space usage

Recursive + Memoization

🟑 O(K Γ— N)

πŸ”΄ O(K Γ— N)

Natural recursion flow

Stack overhead

βœ… Best Choice?

  • If optimizing space: Use 1D DP (Space-Optimized).

  • If space is not a concern: Use 2D DP (Tabulation) for easier understanding.

  • For recursion lovers: Use Recursive + Memoization.

Code (Java)

class Solution {
    public static int maxProfit(int[] prices, int k) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;
        if (2 * k >= n) {
            int profit = 0;
            for (int i = 1; i < n; i++)
                profit += Math.max(0, prices[i] - prices[i - 1]);
            return profit;
        }
        int[] dp = new int[2 * k + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[0] = 0;
        for (int price : prices)
            for (int j = 1; j <= 2 * k; j++)
                dp[j] = (j % 2 == 1) ? Math.max(dp[j], dp[j - 1] - price) : Math.max(dp[j], dp[j - 1] + price);
        return dp[2 * k];
    }
}

Code (Python)

class Solution:
    def maxProfit(self, prices, k):
        n = len(prices)
        if n == 0 or k == 0:
            return 0
        if 2 * k >= n:
            return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))
        dp = [-float('inf')] * (2 * k + 1)
        dp[0] = 0
        for price in prices:
            for j in range(1, 2 * k + 1):
                dp[j] = max(dp[j], dp[j - 1] - price) if j % 2 else max(dp[j], dp[j - 1] + price)
        return dp[2 * k]

Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐


πŸ“Visitor Count

Last updated