121. Best Time to Buy and Sell Stock¶
Given an array prices where prices[i] is the price of a given stock on the ith day. Return the maximum profit that can be achieved by buying on one day and selling on another.
Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Intuition¶
- To identify the max profit, we need to buy on the day when price is lowest & sell on the day its highest till the day
i.
Approach¶
- Iterate over the array store the
minPrice&maxPriceseen till now. - If we have to change the
minPriceit mean we are buying on that day somaxPricealso needs to be reset.
Complexity¶
- Time complexity : \(\text{O}(n)\)
- We iterate over the prices only once.
- Space complexity : \(\text{O}(1)\)
- There is no extra space needed.
Code¶
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE, maxPrice = Integer.MIN_VALUE,maxProfitTillNow = 0;
for (int i = 0; i < prices.length; ++i) {
// If current day price is the lowest
// reset the maxPrice also as it means we are buying on current day
if(prices[i] < minPrice ) {
minPrice = prices[i];
maxPrice = prices[i];
} else {
// Update the maxPrice by comparing price with current day price
maxPrice = Math.max(maxPrice,prices[i]);
// Recalculate the max profit we can achieve till date
maxProfitTillNow = Math.max(maxProfitTillNow,maxPrice-minPrice);
}
}
return Math.max(maxProfitTillNow,maxPrice - minPrice);
}