Buy & Sell Stocks (Unlimited Transactions)

Problem Statement

You are given an integer array prices where prices[i] represents the price of a stock on the i-th day.

On each day, you may buy and/or sell the stock. You can hold at most one share of the stock at any time, but you are allowed to buy and sell on the same day. Return the maximum profit you can achieve.

Problem Breakdown

We can represent this problem using recursion based on the current day (index) and the current state (holding or not):

• At each index, we have two choices:

  1. Take action (buy or sell, depending on the state)

  2. Do nothing (move to the next day with the same state)

We define state as:

Brute Force (Recursive)

Intuition

At every day, we try all possibilities recursively:

• If we can buy → choose to buy or skip.

• If we can sell → choose to sell or skip.

Code

Copyint profit(vector<int>& prices, int index, int state) {
    if (index == prices.size()) return 0;

    int skip = profit(prices, index + 1, state);  // Do nothing

    int action = 0;
    if (state == 0) {
        // Buy the stock
        action = -prices[index] + profit(prices, index + 1, 1);
    } else {
        // Sell the stock
        action = prices[index] + profit(prices, index + 1, 0);
    }

    return max(skip, action);
}

int maxProfit(vector<int>& prices) {
    return profit(prices, 0, 0);  // Start at day 0, with permission to buy
}

Time Complexity: O(2^n)

Too slow for large inputs due to repeated subproblems.

Memoization (Top-Down DP)

Idea

Store results of subproblems in a 2D dp table to avoid recomputation. Dimensions:

• index = day number

• state = 0 or 1 (not holding / holding)

Code

Copyint profit(vector<int>& prices, vector<vector<int>>& dp, int index, int state) {
    if (index == prices.size()) return 0;

    if (dp[index][state] != -1) return dp[index][state];

    int skip = profit(prices, dp, index + 1, state);  // Do nothing

    int action = 0;
    if (state == 0) {
        // Buy the stock
        action = -prices[index] + profit(prices, dp, index + 1, 1);
    } else {
        // Sell the stock
        action = prices[index] + profit(prices, dp, index + 1, 0);
    }

    return dp[index][state] = max(skip, action);
}

int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<vector<int>> dp(n, vector<int>(2, -1));  // dp[day][state]
    return profit(prices, dp, 0, 0);  // Start at day 0, can buy
}

Time Complexity: O(n * 2)

Space Complexity: O(n * 2) (can be optimized with tabulation and space compression)

Summary