Last Updated: 2 Sep, 2022
Best time to buy and sell stock
Moderate
Asked in companies
You are given an array of integers 'prices' of size 'n', where ‘prices[i]’ is the price of a given stock on an ‘i’-th day. You want to maximize the profit by choosing a single day to buy one stock and a different day to sell that stock.
Please note that you can’t sell a stock before you buy one.
Input Format :
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 from this transaction.
Constraints :
1 <= 'n' <= 10 ^ 5
1 <= ‘prices[i]’<= 10 ^ 9
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, and keep updating the maximum profit so far.
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.
The steps are as follows:-
- Initialize ‘maxProfit’ with 0.
- Use two nested loops. The outer one will consider the day the stock will be purchased, and the inner one will consider the days on which the stock will be sold.
- Find the maximum profit by buying and selling at each index. At each iteration, find the profit. Change the value of the ‘maxProfit’ if the yield obtained is greater than the ‘maxProfit’.
- Return the maximum profit.
It is always profitable to buy a stock when its price is the lowest in the past.
Taking an example for understanding, ‘prices’ = [7, 1, 5, 4, 3, 6].
Max profit on Day 3 = Stock price on Day 3 - Minimum of the Stock price of Day 1 and Day 2 = 5 - 1 = 4.
Max profit on Day 4 = Stock price on Day 4 - Minimum of the Stock price of Day 1, Day 2, and Day 3 = 4 - 1 = 3.
In general, max profit on Day n = Price of stock on Day n - min(Day 1, Day 2, ………., Day n-1).
So our idea is to buy the stock at the lowest price that has occurred in the past and sold it on the current day. This operation can be performed on every possible day and the maximum profit among them can be stored as the answer to the problem.
To achieve it, we iterate over the ‘prices’ array linearly and keep a variable storing the value of the least price that has occurred in the past.
We calculate the profit if we sell at the current point of time and buy at the least price in the past, and update our maximum profit.
The steps are as follows:
- Make two variables, ‘maxProfit’ = 0, to store the maximum profit and ‘minCost’ = ‘Integer.MAX_VALUE’ to store the minimum price of stock till the ‘i’th day.
- Linearly traverse the stock PRICES array.
- Keep track of the minimum element on the left side.
- Calculate the profit on an ‘i’th day, considering that we are selling the stock on the ‘i’th day, and purchasing the stock at the minimum price until the ith day. Update the ‘maxProfit’ value if the profit exceeds the maxProfit.
- Return the ‘maxProfit’.