Buy and Sell Stock
You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘N’ days. You can either buy or sell a stock. Also, you can only complete at most 2-transactions. Find the maximum profit that you can earn from these transactions. You can take help from Mr. Mehta as well.

Note

1. Buying a stock and then selling it is called one transaction. 2. You are not allowed to do multiple transactions at the same time. This means you have to sell the stock before buying it again.

Input Format:

The first line contains a single integer 'T' representing the number of test cases. Then 'T' test cases follow: The first line of each test case contains an integer 'N' denoting the number of days. The second line of each test case contains 'N' space-separated integers, where the 'i-th' element is the price of the particular stock on the 'i-th' day.

Output Format :

For each test case, the first and only line of output contains an integer denoting the maximum profit. The output of every test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Buy and Sell Stock

You are Harshad Mehta’s friend. He told you the price of a particular stock for the next ‘N’ days. You can either buy or sell a stock. Also, you can only complete at most 2-transactions. Find the maximum profit that you can earn from these transactions. You can take help from Mr. Mehta as well.

Note

1. Buying a stock and then selling it is called one transaction. 
2. You are not allowed to do multiple transactions at the same time. This means you have to sell the stock before buying it again.

Input Format:

The first line contains a single integer 'T' representing the number of test cases.      
Then 'T' test cases follow:

The first line of each test case contains an integer 'N' denoting the number of days. 

The second line of each test case contains 'N' space-separated integers, where the 'i-th' element is the price of the particular stock on the 'i-th' day.

Output Format :

For each test case, the first and only line of output contains an integer denoting the maximum profit. 

The output of every test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 5 * 10^4
0 <= price <= 10^3

Where ‘price’ is the price of the stock on each day. 

Time Limit: 1 sec

Accepted Answer

Recursion

This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion.

Basically, we have to buy the stock at the minimum possible price and sell at the maximum possible price, keeping in mind that we have to sell the stock before buying it again.

Below is the detailed algorithm:

Call a recursive function ‘maxProfitHelper’ by passing four parameters i.e. ‘PRICES’, starting index, number of transactions, and a boolean variable ‘ISBOUGHT’. ‘ISBOUGHT’ will help us in engaging in just one transaction at a time. Initially, ‘ISBOUGHT’ is false.

maxProfitHelper(‘PRICES’, ‘INDEX’, ‘TRANS’, ‘ISBOUGHT’):

Base Condition: When we are out of days, or the transactions left are 0, return 0 as you can not do anything.
Now we have three options:
- If ‘ISBOUGHT’ is false:
  - Buy the stock: Recursively find the profit made by the remaining items by setting ‘ISBOUGHT’ as true and ‘INDEX’ as ‘INDEX’ + 1. Note that buying a stock is a loss of ‘PRICES[INDEX]’.
- If ‘ISBOUGHT’ is true:
  - Sell the stock: Recursively find the profit made by the remaining items by decreasing the transactions by 1 and ‘INDEX’ as ‘INDEX’ + 1. Note that selling a stock is a profit of ‘PRICES[INDEX]’.
- Skip the day, Recursively find the profit made by the remaining items by setting ‘INDEX’ as ‘INDEX’ + 1.
Return the maximum profit obtained by any of the above options.

Space Complexity: O(n)Explanation:

O(N), where N is the number of days.

We are not using any external data structure. Only recursion stack space of O(N) size is used by the algorithm.

Time Complexity: O(2^n)Explanation:

O(2 ^ N), where N is the number of days.

We have three options each day; either skip the day, buy on that day or sell on that day. But we can only engage in one transaction at a time, each recursive call ends up in two recursive calls, thus the final time complexity will be O(2 ^ N).

Accepted Answer

Memoization

We are solving this problem by solving its subproblems and then combining the solutions of those subproblems. If we analyze carefully, we will see that we are solving the same subproblems multiple times. Thus, this problem exhibits overlapping subproblems. Thus, in this approach, we will eliminate the need for solving the same subproblems again and again.

Below is the detailed algorithm:

The idea is to use memoization.

Create a 3-D lookup table of size (2 * 3 * ('N')), where ‘N’ is the number of days. Lookup table stores the solutions to the subproblems where ‘LOOKUP[ISBOUGHT][TRAN][INDEX]’ denotes the maximum profit you can earn by doing at most ‘TRAN’ transactions in first 'INDEX' days.
Initialize the table by -1.
Now, we will call a recursive function ‘maxProfitHelper’ by passing five parameters i.e. ‘PRICES’, starting index, number of transactions, and a boolean variable ‘ISBOUGHT’, and the ‘LOOKUP’ table. ‘ISBOUGHT’ will help us in engaging in just one transaction at a time. Initially, ‘ISBOUGHT’ is false.

maxProfitHelper('PRICES', ‘INDEX', ‘TRAN’, ‘ISBOUGHT’, ‘LOOKUP’):

Base Condition: When we are out of days, or the transactions left are 0, return 0 as you can not do anything.
If the current subproblem has been solved already, return the value stored in the ‘LOOKUP’ table.
Now we have three options:
- If 'ISBOUGHT' is false:
  - Buy the stock: Recursively find the profit made by the remaining items by setting ‘ISBOUGHT’ as true and 'INDEX' as 'INDEX' + 1. Note that buying a stock is a loss of ‘PRICES[INDEX]’.
- If ‘ISBOUGHT’ is true:
  - Sell the stock: Recursively find the profit made by the remaining items by decreasing the transactions by 1 and 'INDEX' as 'INDEX' + 1. Note that selling a stock is a profit of ‘PRICES[INDEX]’.
- Skip the day, Recursively find the profit made by the remaining items by setting 'INDEX' as 'INDEX' + 1.
Store the maximum profit obtained by any of the above options into the ‘LOOKUP’ table and finally return it.

Space Complexity: O(n)Explanation:

O(N), where N is the number of days.

Since we are using a table ‘maxProfit’ of size (2) * (3) * (N), the final space complexity is O(2 * 3 * N) = O(N).

Time Complexity: O(n^2)Explanation:

O(N ^ 2), where N is the number of days.

We have three options each day; either skip the day, buy on that day or sell on that day. But we can only engage in one transaction at a time, each recursive call ends up in two recursive calls. Also, there can only be O(2 * N * N) different subproblems. Thus, the final time complexity will be O(2 * N * N) = O(N * N) = O(N ^ 2).

Java (SE 1.8)

/*

	Time Complexity: O(N ^ 2)

	Space Complexity: O(N)



	Where N is the number of days.

*/



import java.util.ArrayList;



public class Solution {



    public static int maxProfitHelper(ArrayList prices, int index, int tran, int isBought, int[][][] lookUp) {

        // Base Condition.

        if(index == prices.size() || tran == 0)

        {

            return 0;

        }



        // If we have already solved this subproblem.

        if(lookUp[isBought][tran][index] != -1)

        {

            return lookUp[isBought][tran][index];

        }



        // Max profit if we skip the current day.

        int result = maxProfitHelper(prices, index + 1, tran, isBought, lookUp);



        if(isBought == 0)

        {

            // Max profit if we buy the stock on the current day.

            result = Math.max(result, maxProfitHelper(prices, index + 1, tran, 1, lookUp) - prices.get(index));

        } 

        else

        {

            // Max profit if we sell the stock on the current day.

            result = Math.max(result, maxProfitHelper(prices, index + 1, tran - 1, 0, lookUp) + prices.get(index));

        }



        // Store the result.

        lookUp[isBought][tran][index] = result;



        // Return final maximum profit .

        return result;

    }





	public static int maxProfit(ArrayList prices, int n) {

        // Look up table.

        int[][][] lookUp = new int[2][3][n];



        for(int i = 0; i<2; i++)

        {

            for(int j = 0; j<3; j++)

            {

                for(int k = 0; k                {

                    lookUp[i][j][k] = -1;

                }

            }

        }



        return maxProfitHelper(prices, 0, 2, 0, lookUp);

    }

}

Python (3.5)

'''

	Time Complexity: O(N ^ 2)

	Space Complexity: O(N)



	Where N is the number of days.

'''





def maxProfitHelper(prices, index, tran, isBought, lookUp):



    # Base Condition.

    if(index == len(prices) or tran == 0):

        return 0



    # If we have already solved this subproblem.

    if(lookUp[isBought][tran][index] != -1):

        return lookUp[isBought][tran][index]



    # Max profit if we skip the current day.

    result = maxProfitHelper(prices, index + 1, tran, isBought, lookUp)



    if(isBought == False):



        # Max profit if we buy the stock on the current day.

        result = max(result, maxProfitHelper(

            prices, index + 1, tran, True, lookUp) - prices[index])



    else:



        # Max profit if we sell the stock on the current day.

        result = max(result, maxProfitHelper(prices, index + 1,

                                             tran - 1, False, lookUp) + prices[index])



    # Store the result.

    lookUp[isBought][tran][index] = result



    # Return final maximum profit.

    return result





def maxProfit(prices, n):



    # Look up table.

    lookUp = [[[-1 for i in range(n)] for j in range(3)] for k in range(2)]

    return maxProfitHelper(prices, 0, 2, False, lookUp)

C++ (g++ 5.4)

/*

	Time Complexity: O(N ^ 2)

	Space Complexity: O(N)



	Where N is the number of days.

*/



int maxProfitHelper(vector& prices, int index, int tran, bool isBought, vector>>& lookUp)

{

	// Base Condition.

	if(index == prices.size() or tran == 0)

	{

		return 0;

	}



	// If we have already solved this subproblem.

	if(lookUp[isBought][tran][index] != -1)

	{

		return lookUp[isBought][tran][index];

	}



	// Max profit if we skip the current day.

	int result = maxProfitHelper(prices, index + 1, tran, isBought, lookUp);



	if(isBought == false)

	{

		// Max profit if we buy the stock on the current day.

		result = max(result, maxProfitHelper(prices, index + 1, tran, true, lookUp) - prices[index]);

	} 

	else

	{

		// Max profit if we sell the stock on the current day.

		result = max(result, maxProfitHelper(prices, index + 1, tran - 1, false, lookUp) + prices[index]);

	}



	// Store the result.

	lookUp[isBought][tran][index] = result;



	// Return final maximum profit .

	return result;

}





int maxProfit(vector& prices, int n)

{

	// Look up table.

	vector>>lookUp(2, vector>(3, vector(n, - 1)));



    return maxProfitHelper(prices, 0, 2, false, lookUp);

}

Accepted Answer

Dynamic Programming

The idea is to create a 2-D array ‘MAXPROFIT’ of size size (3) * (N).
Initially, all the elements of the ‘MAXPROFIT’ matrix will be 0.
Now, the value ‘MAXPROFIT[i][j]’ denotes the maximum profit we can earn by doing 'i' transactions upto ‘j-th’ day.

The detailed algorithm to fill the ‘MAXPROFIT’ matrix is as follows:

L1 : Run a loop from ‘k’ = 1 to 2 to consider the both transactions:
- Select the ‘MINVALUE’ as 'PRICES[0]'.
- L2 : Run a loop from ‘i’ = 1 to N to consider the prices of each day:
  For the ‘kth’ transaction,
  - If we don’t trade on the ‘i-th’ day, then the profit will be the same as the ‘i-1th’ day.
  - If we buy the stock on ‘j-th’ day [ j < i ] and sell on the ‘i-th’ day, then the profit is (‘PRICES[i]’ - ‘PRICES[j]’) + ‘MAXPROFIT[k - 1][j - 1]’.
  - Thus, update:
    ‘MINVALUE’ = min(‘MINVALUE’ , ‘PRICES[i]’ - ‘MAXPROFIT[k - 1][i - 1]')
    ‘MAXPROFIT[k][i]’ = max( ‘MAXPROFIT[k][i - 1]' , ‘PRICES[i]’ - ‘MINVALUE’).
    Also note that L1 and L2 will be two nested loops.
Return ‘MAXPROFIT[2][N - 1]’, the final profit that can be earned.

Space Complexity: O(1)Explanation:

O(N), where N is the number of days.

Since we are using a table ‘maxProfit’ of size (2) * (N), the final space complexity is O(2 * N) = O(N).

Time Complexity: O(n)Explanation:

O(N), where N is the number of days.

For each transaction [ 2 choices ], we are considering the stocks for N days. [ O(N) choices ]. Thus, the final time complexity is O(2 * N) = O(N).

Python (3.5)

'''

	Time Complexity: O(N)

	Space Complexity: O(N)



	Where N is the number of days.

'''





def maxProfit(prices, n):



    maxProfit = [[0 for i in range(n)] for j in range(3)]



    # Loop to consider both transactions.

    for k in range(1, 3):

        minValue = prices[0]



        # Loop to consider prices of each day.

        for i in range(1, n):



            # Set the buying price.

            minValue = min(minValue, prices[i] - maxProfit[k - 1][i - 1])



            # Update the profit.

            maxProfit[k][i] = max(maxProfit[k][i - 1], prices[i] - minValue)



    # Return the final maximum profit.

    return maxProfit[2][n - 1]

Java (SE 1.8)

/*

	Time Complexity: O(N)

	Space Complexity: O(N)



	Where N is the number of days.

*/



import java.util.ArrayList;



public class Solution {

	public static int maxProfit(ArrayList prices, int n) {

        

        int[][] maxProfit = new int[3][n];



        // Loop to consider both transactions.

        for (int k = 1; k <= 2; k++)

        {

            int minValue = prices.get(0);



            // Loop to consider prices of each day.

            for (int i = 1; i < n; i++)

            {

                // Set the buying price.

                minValue = Math.min(minValue, prices.get(i) - maxProfit[k - 1][i - 1]);



                // Update the profit. 

                maxProfit[k][i] = Math.max(maxProfit[k][i - 1], prices.get(i) - minValue);

            }

        }

        // Return the final maximum profit.

        return maxProfit[2][n - 1];

    }

}

C++ (g++ 5.4)

/*

	Time Complexity: O(N)

	Space Complexity: O(N)



	Where N is the number of days.

*/



int maxProfit(vector& prices, int n)

{

    vector> maxProfit(3, vector(n, 0));



    // Loop to consider both transactions.

    for (int k = 1; k <= 2; k++)

    {

        int minValue = prices[0];



        // Loop to consider prices of each day.

        for (int i = 1; i < n; i++)

        {

        	// Set the buying price.

            minValue = min(minValue, prices[i] - maxProfit[k - 1][i - 1]);



            // Update the profit. 

            maxProfit[k][i] = max(maxProfit[k][i - 1], prices[i] - minValue);

        }

    }

    // Return the final maximum profit.

    return maxProfit[2][n - 1];

}

Accepted Answer

Optimized Dynamic Programming

We observe that the approach for the question goes in the following way:

First buy → First sell → Second buy → Second sell

Now, as, at the end we need maximum profit, let us think of it like this. Suppose, you currently have Rs. 100 with you. You buy a stock of some amount say ‘X’. The amount left with you is 100 - ‘X’ . Now, you sell the stock at an amount say ‘ Y ‘, you are left with a total amount of 100 - ‘X’ + ‘Y’.

During the second transaction, you buy a stock of price ‘A’ and sell it at price ‘B’. The total amount becomes 100 - ‘X’ + ‘Y’ - ‘A’ + ‘B’. Now, all you need to do is maximize the money that you have.

Below is the detailed algorithm:

Initialize variables 'FIRSTBUY' as the minimum negative value, ‘FIRSTSELL’ as 0, ‘SECONDBUY’ as the minimum negative value, and ‘SECONDSELL’ as 0.
‘FIRSTSELL’ will be the profit after the first transaction and ‘SECONDSELL’ will be the profit after the second transaction.
For ‘i’ in range days:
- Maximise 'FIRSTBUY' as max( 'FIRSTBUY' , - ‘PRICES[i]’), this is the amount left after your first buy.
- Maximise ‘FIRSTSELL’ as max( ‘FIRSTSELL’ , 'FIRSTBUY' + ‘PRICES[i]’).
- Maximise ‘SECONDBUY’ as max( ‘SECONDBUY’ , ‘FIRSTSELL’ - ‘PRICES[i]’).
- Maximise ‘SECONDSELL’ as max( ‘SECONDSELL’ , ‘SECONDBUY’ + ‘PRICES[i]’).
Return ‘SECONDSELL’ as it is the final profit or the final amount left with you.

Space Complexity: O(1)Explanation:

O(1)

We are not using any extra data structure. Only constant space is used by the algorithm.

Time Complexity: O(n)Explanation:

O(N), where N is the number of days.

We are traversing the prices array only once and doing atmost 2 transactions in a single pass. Thus, the time complexity is O(N).

C++ (g++ 5.4)

/*

	Time Complexity: O(N)

	Space Complexity: O(1)



	Where N is the number of days.

*/



#include 



int maxProfit(vector &prices, int n)

{

	int firstBuy = INT_MIN, firstSell = 0;

	int secondBuy = INT_MIN, secondSell = 0;



	// Loop to consider each day.

	for (int i = 0; i < n; i++)

	{

		// Maximum profit after buying the stock for the first time.

		firstBuy = max(firstBuy, -prices[i]);



		// Maximum profit after selling the stock for the first time.

		firstSell = max(firstSell, firstBuy + prices[i]);



		// Maximum profit after buying the stock for the second time.

		secondBuy = max(secondBuy, firstSell - prices[i]);



		// Maximum profit after selling the stock for the second time.

		secondSell = max(secondSell, secondBuy + prices[i]);

	}



	// Return the final profit.

	return secondSell;

}

Java (SE 1.8)

/*

	Time Complexity: O(N)

	Space Complexity: O(1)



	Where N is the number of days.

*/



import java.util.ArrayList;



public class Solution {

	public static int maxProfit(ArrayList prices, int n) {

        

        int firstBuy = Integer.MIN_VALUE, firstSell = 0;

        int secondBuy = Integer.MIN_VALUE, secondSell = 0;



        // Loop to consider each day.

        for (int i = 0; i < n; i++)

        {

            // Maximum profit after buying the stock for the first time.

            firstBuy = Math.max(firstBuy, -1*prices.get(i));



            // Maximum profit after selling the stock for the first time.

            firstSell = Math.max(firstSell, firstBuy + prices.get(i));



            // Maximum profit after buying the stock for the second time.

            secondBuy = Math.max(secondBuy, firstSell - prices.get(i));



            // Maximum profit after selling the stock for the second time.

            secondSell = Math.max(secondSell, secondBuy + prices.get(i));

        }



        // Return the final profit.

        return secondSell;

    }

}

Python (3.5)

'''

	Time Complexity: O(N)

	Space Complexity: O(1)



	Where N is the number of days.

'''



from sys import maxsize





def maxProfit(prices, n):



    firstBuy, firstSell = -maxsize, 0

    secondBuy, secondSell = -maxsize, 0



    # Loop to consider each day.

    for i in range(n):



        # Maximum profit after buying the stock for the first time.

        firstBuy = max(firstBuy, - prices[i])



        # Maximum profit after selling the stock for the first time.

        firstSell = max(firstSell, firstBuy + prices[i])



        # Maximum profit after buying the stock for the second time.

        secondBuy = max(secondBuy, firstSell - prices[i])



        # Maximum profit after selling the stock for the second time.

        secondSell = max(secondSell, secondBuy + prices[i])



    # Return the final profit.

    return secondSell

Note

Input Format:

Output Format :

Note:

Constraints:

Top Goldman Sachs Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Goldman Sachs Software Developer