Best Time to Buy and Sell Stock
Given an array where the element at the index i represents the price of a stock on day i, find the maximum profit that you can gain by buying the stock once and then selling it.
Given an array where the element at the index i represents the price of a stock on day i, find the maximum profit that you can gain by buying the stock once and then selling it.
Note
You can buy the stock on one specific day and sell it on a different day to make a profit. If no profit can be achieved, we return zero.
Constraints
- We can't sell before buying a stock, that is, the array index at which stock is bought will always be less than the index at which the stock is sold.
- 1 ≤
prices.length≤ 10³ - 0 ≤
prices[i]≤ 10⁵
Examples
Sample Example 1
Input:
prices= [7, 1, 5, 3, 6, 4]
Output: Profit = 5
Explanation: The stock will be purchased on Day 2 and then sold on Day 5 to maximize profit.
Sample Example 2
Input:
prices= [7, 6, 4, 3, 1]
Output: Profit = 0
Explanation: No profit can be generated with this sequence of stock prices.
Solution
If we sell at ith price if we want to make profit, we'll look for minimum price between index 0 to i-1. So we'll keep track of minimum price from 0 to i-1 and maximum profit with that price.
function maxProfit(prices){
let minPrice =Infinity;
let maxProfit= -Infinity;
for (let i=0; i<prices.length; i++){
minPrice =Math.min(minPrice ,prices[i]);
maxProfit=Math.max(maxProfit,prices[i]-minPrice )
}
return maxProfit;
}
console.log(maxProfit([7, 6, 4, 3, 1]));
Time Complexity: O(N)
Space Complexity: O(1)