Best Time to Buy and Sell Stock II

Moderate
0/80
Average time to solve is 22m
profile
Contributed by
168 upvotes
Asked in companies
PhonePeAmazonFacebook

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
1
7
1 2 3 4 5 6 7
Sample Output 1 :
6
Explanation :
We can make the maximum profit by buying the stock on the first day and selling it on the last day.
Sample Input 2 :
1
7
7 6 5 4 3 2 1
Sample Output 2 :
0
Explanation :
We can make the maximum profit by not buying the stock.
Hint

Try to consider all possibilities of buying and selling stocks and see which one gives you the maximum profit.

Approaches (2)
Brute Force Approach

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, 

  1. We run a loop indicating the buying day. For every day when a stock is bought,
  2. We run a nested loop to try all the combination of days on which the stock was sold.
    1. 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.
    2. Recursively get the value of profit for the rest of the values assuming neither the stocks were bought and nor were the sold.
  3. Get the max profit value out of all the combinations.
Time Complexity

O(N ^ N), Where N is the total number of days
 

Since for every index, you recurse on the array from that index till the end

Space Complexity

O(N), Where N is the total number of days
 

Since at any time the maximum functions call that would exist in the stack will be N

Code Solution
(100% EXP penalty)
Best Time to Buy and Sell Stock II
Full screen
Console