Last Updated: 10 Jul, 2020
Best Time to Buy and Sell Stock II
Moderate
Asked in companies
You have been given stock values/prices for N number of days. Every i-th day signifies the price of a stock on that day. Your task is to find the maximum profit which you can make by buying and selling the stocks.
Note :
You may make as many transactions as you want but can not have more than one transaction at a time i.e, if you have the stock, you need to sell it first, and then only you can buy it again.
Input format :
The first line contains an integer 't' which denotes the number of test cases or queries to be run. Then the test cases follow.
The first line of each test case or query contains an integer 'N' representing the total number of days for which you have stock prices.
The second line contains 'N' single space-separated integers representing the price of the stock on i-th day.
Output Format :
For each test case, print the maximum profit that you can earn.
Output for every test case will be printed in a separate line.
Note :
You are not required to print anything explicitly. Just implement the function.
Constraints :
1 <= t <= 10^2
0 <= N <= 10^5
Time Limit: 1 sec
Approaches
Let's say we have stock values of two days, say, [20, 30].
One must have to buy the stock first in order to sell it in the coming days.
So,
1. if I choose to buy the stock on first day for a value of 20 and sell it on the second day for a value of 30, I can earn a max profit of 10.
2. If I chose to skip day 1, then buying the stock on day 2 will put me in lose since there are no further days on which I can sell the stock. Hence, in this case, day 2 has to be skipped in order to make a max profit of 0.
Among these two scenarios, the first case yields me maximum profit and hence the answer.
This means, for every day, I may choose to buy or skip the stock. Once bought, I have to sell it in the following days to yield a max profit. Hence, to explore all the different possibilities,
- We run a loop indicating the buying day. For every day when a stock is bought,
- We run a nested loop to try all the combination of days on which the stock was sold.
- If the value of the stock on buying day is less than the value of the stock on the day bought, we have a profit.
- Recursively get the value of profit for the rest of the values assuming neither the stocks were bought and nor were the sold.
- Get the max profit value out of all the combinations.
- Keep a ‘profit’ variable to keep track of the total profit earned
- Check the stock prices of every two consecutive days with a loop
- If the price on the second day is more than that of the first day, add their price's difference to ‘profit’
- Return profit
Similar problems