Best Time to Buy and Sell Stock
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) Example 2: Input: [7, 6, 4, 3, 1] Output: 0
In this case, no transaction is done, i.e. max profit = 0.
Solution: Find the local max price to the right of the current day
If we are allowed to buy and sell only once, then we can use following algorithm: Maximum difference between two elements.
In this method, instead of taking difference of the picked element with every other element, we take the difference with the minimum element found so far. So we need to keep track of 2 things:
- Maximum difference found so far.
- Minimum number visited so far.
Note: we can start from either the front or end.
int maxProfit(vector<int>& prices) {
if(prices.size() <=1) return 0;
int maxPrice = INT_MIN;
int maxProfit = INT_MIN;
for(int i=prices.size()-1; i>=0; i--) {
maxPrice = max(maxPrice, prices[i]);
maxProfit = max(maxProfit, maxPrice - prices[i]);
}
return maxProfit;
}