Best time to buy and sell stock II

Moderate
0/80
profile
Contributed by
4 upvotes
Asked in company
Unthinkable Solutions LLP

Problem statement

You are given an array of integers, 'PRICES' of size 'N', where 'PRICES[i]' is the price of a given stock on 'i'th day.

On each day, you may decide to buy and sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it and then immediately sell it on the same day.

Return the maximum profit you can achieve.

Note: You can't sell a stock before you buy one.

Example: 
Let's say, 'PRICES' = [7, 1, 5, 4, 3, 6]

Purchase stock on day two, where the price is one, and sell it on day three, where the price is five, profit = 5 - 1 = 4.
Purchase stock on day five, where the price is three, and sell it on day six, where the price is six, profit = 6 - 3 = 3.
Total Profit is 4+3 = 7. Hence we return 7.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
First-line contains 'T', denoting the number of Test cases.

For each Test case:

The first line contains an integer 'N' denoting the size of the array 'PRICES'.
The second line includes 'N' integers denoting the elements of the array 'PRICES'.
Output format : 
Return the maximum profit you can achieve.
Note:- 
You don't need to print anything. Just implement the given function.
Constraints : 
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1<= 'PRICES[i]' <= 10^9, 0 <= i <= 'N-1'

Time Limit: 1 sec
Sample Input 1 :
2
6
7 1 5 4 3 6
6
100 160 220 40 535 695
Sample Output 1 :
7
775
Explanation Of Sample Input 1 :
For test case 1:

'PRICES' = [7, 1, 5, 4, 3, 6]

Purchase stock on day two, where the price is one, and sell it on day three, where the price is five, profit = 5 - 1 = 4.
Purchase stock on day five, where the price is three, and sell it on day six, where the price is six, profit = 6 - 3 = 3.
Total Profit is 4+3 = 7. Hence we return 7.

For test case 2:

'PRICES' = [100, 160, 220, 40, 535, 695]

Purchase stock on day one, where the price is 100, and sell it on day three, where the price is 220, profit = 220 - 100 = 120.
Purchase stock on day four, where the price is 40, and sell it on day six, where the price is 695, profit = 695 - 40 = 655.

Total Profit is 120+655 = 775. Hence we return 775.
Sample Input 2 :
2
5
5 4 3 2 1
1
13
Sample Output 2 :
0
0
Hint

Try out all possible ways to buy and sell the stocks.


 

Approaches (2)
Naive

As seen from the sample input-output examples, a possible approach would be to buy a stock, sell it on every possible day whenever profitable, repeat the same process for the rest of the days and keep track of the maximum profit.

This will require two nested loops. The outer one will pick up each day, say ‘i’, one by one to purchase that stock, and the inner loop will calculate the profit if the stock is sold on each possible day ‘j’, then call a recursion to get an answer from days after ‘j’.

 

The steps are as follows:-

 

// Recursive function to find the maximum profit

function  evaluateProfit([int] PRICES, int startIndex):

 

  1. Int  ‘N’ is the length of array ‘PRICES’.
  2. If startIndex==N
    • Return 0
  3. Initialise maxProfitFin = 0
  4. Run a loop from 'i' = startIndex... 'N' - 1:
    • Initialise maxProfit = 0
    • Again Run a loop from 'j' = 'i+1'... 'N' -1:
      • If PROFIT[j] > PROFIT[i] :
        • Initialise curProfit with PROFIT[j] - PROFIT[i].
        • Add  evaluateProfit(PROFIT ,j+1) to curProfit
        • maxProfit is the maximum of maxProfit and curProfit.
    • maxProfitFin is the maximum of maxProfitFin and maxProfit.
  5. Return maxProfitFin.

 

function bestTimeToBuyAndSellStock( [int] PRICES ):

  1. Return evaluateProfit(PRICES, 0).
Time Complexity

O(N^N), where 'N' is the array ‘PRICES’ length.

 

We are making a recursive call at each of the ‘N’ days.


Hence overall time complexity is O(N^N).


 

Space Complexity

O(N), Where ‘N’ is the depth of the recursive call.
 

We are making recursive calls that may reach a maximum depth of ‘N’. 

 

Hence the space complexity is O(N).


 

Code Solution
(100% EXP penalty)
Best time to buy and sell stock II
Full screen
Console