Say you have an array for which the i-th 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.
A smart way is to record the minimum buy-in price before dayi , and the maximum profit by selling the stock on day i would be their difference.
A smart way is to record the minimum buy-in price before day
public int maxProfit(int[] prices) {
if(prices==null || prices.length==0)
return 0;
int lowestBuyInPrice = prices[0]; // Lowest buy-in price up to now
int maximumProfit = 0; // Maximum profit up to now
for (int i = 1; i < prices.length; i++) {
// Update the maximum profit if buying the stock with the lowest price up to now and
// selling it in day i makes greater profit
maximumProfit = Math.max(maximumProfit, prices[i]-lowestBuyInPrice);
// Update the lowest price if the price in day i is smaller than those in earlier days
lowestBuyInPrice = Math.min(lowestBuyInPrice, prices[i]);
}
return maximumProfit;
}
Read full article from LeetCode - Best Time to Buy and Sell Stock | Darren's Blog
No comments:
Post a Comment