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

The idea is to traverse the given list of prices and find a local minimum of every increasing sequence. We can gain maximum profit if we buy the shares at the starting of every increasing sequence (local minimum) and sell them at the end of the increasing sequence (local maximum).
Steps :
1. Find the local minima and store it as starting index. If not exists, return.
2. Find the local maxima. and store it as an ending index. If we reach the end, set the end as the ending index.
3. Update the solution and Increment count of buy-sell pairs.
4. Repeat the above steps till the end is not reached.

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);

}

Top Info Edge Senior Software Engineer interview questions & answers

Popular interview questions of Senior Software Engineer

Top HR questions asked in Info Edge Senior Software Engineer