Last Updated: 5 Sep, 2022
Best time to buy and sell stock II
Moderate
Asked in company
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.
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
Approaches
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):
- Int ‘N’ is the length of array ‘PRICES’.
- If startIndex==N
- Return 0
- Initialise maxProfitFin = 0
- 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.
- If PROFIT[j] > PROFIT[i] :
- maxProfitFin is the maximum of maxProfitFin and maxProfit.
- Return maxProfitFin.
function bestTimeToBuyAndSellStock( [int] PRICES ):
- Return evaluateProfit(PRICES, 0).
It is always profitable to buy a stock when its price is lower on the previous day because we can make any number of purchase and sell it.
Taking an example for understanding, ‘PRICES’ = [7, 1, 2, 4, 3, 6].
Buy the stock on day two and sell on day three, making a profit of 2-1=1.
Again buy the stocks on day three and sell them on day four, making a profit of 4-2=2.
These two transactions are equivalent to buying it on day two and selling it on day four. Hence we can break our tractions such that we always buy on the very previous day if the price is higher on the current day.\
Buy the stock on day five and sell on day six, making a profit of 6-3=3.
In general, we buy a stock on day ‘i-1’ and sell it on ‘i’ whenever
PRICES[i] > PRICES[i-1].
To achieve it, we iterate over the ‘PRICES’ array linearly, and whenever we find a day such that the price on the current day is lower than the price of the current day, we buy on the previous day and sell on the current day and add the profit to ‘maxProfit’.
Return the ‘maxProfit’ in the end as the answer.
The steps are as follows:-
- Initialise maxProfit = 0
- Run a loop from 'i' = 1... 'N' - 1:
- If PRICES[i] > PRICES[i-1] add PRICES[i] - PRICES[i-1] to maxProfit.
- Return maxProfit.