Problem Statement

Given an array, arr, of n integers, where arr[i] represents the price of the stock on an ith day, determine the maximum profit achievable by completing at most two transactions in total.

Holding at most one share of the stock at any time is allowed, meaning buying and selling the stock twice is permitted, but the stock must be sold before buying it again. Buying and selling the stock on the same day is allowed.

Examples

Example 1:

Input: arr = [4, 2, 7, 1, 11, 5]
Output: 15

Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 7), profit = 7 - 2 = 5. Then buy on day 4 (price = 1) and sell on day 5 (price = 11), profit = 11 - 1 = 10. Total profit is 5 + 10 = 15.

Example 2:

Input: arr = [1, 3, 2, 8, 4, 9]
Output: 12

Explanation: Buy on day 1 (price = 1) and sell on day 4 (price = 8), profit = 8 - 1 = 7. Then buy on day 5 (price = 4) and sell on day 6 (price = 9), profit = 9 - 4 = 5. Total profit is 7 + 5 = 12.

Different Approaches

1️⃣ Recursive Approach

Upon observation, we find that every day, there will be two choices, either to do nothing and move to the next day or to buy/sell (based on the last transaction and the number of transactions left) and find out the profit. Therefore we need to generate all the choices in order to compare the profit. As all possible choices needs to be generated, we will use recursion.

Steps to form the recursive solution:

• Express the problem in terms of indexes: We need to think in the terms of the number of days, therefore one variable will be the array index( say ind). Next, we need to consider the condition that a stock can't be bought again, that is we need to first sell a stock, and then we can buy that again. Therefore a second variable ‘buy’ is needed, which tells, on a particular day whether we can buy or sell the stock. Next, there is a limit on the number of transactions that can be made. Here the initial cap is 2. So in order to keep track of this constraint, one more variable will be needed (say 'cap').
  f(ind, buy, cap) will give the maximum profit that can be generated from day 'ind' to day (n-1), where 'buy' tells that whether we need to buy or sell the stock at day 'ind' and 'cap' tells the number of transactions left.
• Try out all possible choices at a given index: Every day, there will be two choices, either to buy/sell the stock(based on the buy variable’s value) or to do nothing and move on to the next day. As we need to generate all the choices, use the pick/non-pick technique to the same.
  • Case 1: When buy == 0, the stock can be bought. If we can buy the stock on a particular day, there will be two options:
    • Option 1: To do no transaction and move to the next day. In this case, the net profit earned will be 0 from the current transaction, and to calculate the maximum profit starting from the next day, we will recursively call f(ind+1, 0, cap). As we have not bought the stock, the ‘buy’ variable value will still remain 0, indicating that stock can be bought on next day. And the ‘cap’ variable will remain the same as if no transaction took place.
    • Option 2: The other option is to buy the stock on the current day. In this case, the net profit earned from the current transaction will be -Arr[i]. As we are buying the stock, we are giving money out of our pocket, therefore the profit we earn is negative. To calculate the maximum profit starting from the next day, recursively call f(ind+1,1, cap). As the stock has been bought, the ‘buy’ variable value will change to 1, indicating that we can’t buy and only sell the stock the next day. As we have only bought the stock and not sold it the transaction remains incomplete and the ‘cap’ variable value remains unchanged.
  • Case 2: When buy == 1, we can sell the stock. If we can sell the stock on a particular day, we will have two options:
    • Option 1: To do no transaction and move to the next day. In this case, the net profit earned will be 0 from the current transaction, and to calculate the maximum profit starting from the next day, we will recursively call f(ind+1,1, cap). As we have not bought the stock, the ‘buy’ variable value will still remain at 1, indicating that we can’t buy and only sell the stock the next day. And the ‘cap’ variable will remain the same as if no transaction took place.
    • Option 2: The other option is to sell the stock on the current day. In this case, the net profit earned from the current transaction will be +Arr[i]. As we are selling the stock, we are putting the money into our pocket, therefore the profit we earn is positive. To calculate the maximum profit starting from the next day, we will recursively call f(ind+1,0,cap-1). As we have sold the stock, the ‘buy’ variable value will change to 0, indicating that we can buy the stock the next day. As we have sold the earlier bought stock, we make one complete transaction, therefore now we update the ‘cap’ variable’s value to cap-1.

Note: Buying and selling a stock together counts as one complete transaction.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, buy, cap){
    //Base case
    if(buy == 0){
        op1 = 0 + f(ind + 1, 0, cap)
        op2 = -arr[ind] + f(ind + 1, 1, cap)
    }
    if(buy == 1){
        op1 = 0 + f(ind + 1, 1, cap)
        op2 = arr[ind] + f(ind + 1, 0, cap-1)
    }
           
}

• Take the maximum of all choices: As we are looking to maximize the profit earned, return the maximum value in both cases.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, buy, cap){
    //Base case
    if(buy == 0){
        op1 = 0 + f(ind + 1, 0, cap)
        op2 = -arr[ind] + f(ind + 1, 1, cap)
    }
    if(buy == 1){
        op1 = 0 + f(ind + 1, 1, cap)
        op2 = arr[ind] + f(ind + 1, 0, cap-1)
    }
    return max(op1, op2)    
}

• Base cases:
  • There be will two base cases, when ind==n, it means we have finished trading on all days, and no more profit can be made, therefore simply return 0. Second base case is when cap==0, it means that we cannot make any more transactions. Therefore return 0.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /*
    Helper function to calculate the maximum profit recursively.
    @param day - The current day index.
    @param canBuy - Flag indicating whether a stock can be bought (0 = can buy, 1 = can sell).
    @param remainingTransactions - The number of transactions left (each transaction includes one buy and one sell).
    @param totalDays - The total number of days.
    @param prices - Vector containing stock prices on each day.
    @return Maximum profit that can be achieved from the current state.
    */
    int calculateProfit(int day, int canBuy, int remainingTransactions, int totalDays, vector<int> &prices) {
        // Base case: If all days are processed or no transactions are left
        if (day == totalDays || remainingTransactions == 0) {
            return 0;
        }

        int maxProfit = 0; // Initialize the maximum profit for the current state

        if (canBuy == 0) {
            // Case 1: Option to buy
            maxProfit = max(
                calculateProfit(day + 1, 0, remainingTransactions, totalDays, prices), // Skip buying
                -prices[day] + calculateProfit(day + 1, 1, remainingTransactions, totalDays, prices) // Buy stock
            );
        } else {
            // Case 2: Option to sell
            maxProfit = max(
                calculateProfit(day + 1, 1, remainingTransactions, totalDays, prices), // Skip selling
                prices[day] + calculateProfit(day + 1, 0, remainingTransactions - 1, totalDays, prices) // Sell stock
            );
        }

        return maxProfit; // Return the calculated maximum profit
    }

public:
    /*
    Function to calculate the maximum profit using at most two transactions.
    @param prices - Vector containing stock prices on each day.
    @param totalDays - The total number of days.
    @return Maximum profit that can be achieved with at most two transactions.
    */
    int stockBuySell(vector<int> &prices, int totalDays) {
        if (totalDays == 0) 
            return 0; // If there are no days, profit is 0

        // Start from day 0 with the option to buy and at most 2 transactions allowed
        return calculateProfit(0, 0, 2, totalDays, prices);
    }
};

int main() {
    int totalDays = 8;
    vector<int> stockPrices = {3, 3, 5, 0, 0, 3, 1, 4};

    // Create an instance of the Solution class
    Solution solution;

    // Call the stockBuySell function and display the result
    cout << "The maximum profit that can be generated is " 
         << solution.stockBuySell(stockPrices, totalDays);

    return 0;
}

Complexity Analysis:

• Time Complexity: O(2^(N)), where N is the number of row. As, for each index, there are two possible options.
• Space Complexity: O(N), at maximum the depth of the recursive stack can go up to N.