Question
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.
Stats
| Frequency | 1 |
| Difficulty | 2 |
| Adjusted Difficulty | 2 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
This is a question from a MIT course, Hacking a Google Interview.
I did not solve it, but it’s actually very simple to do.
Solution
The solution is explained here:
To solve this problem efficiently, you would need to track the minimum value’s index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).
Time is O(N)
Code
public int maxProfit(int[] prices) {
int len = prices.length;
if (len <= 1) return 0;
int min = prices[0];
int max = Integer.MIN_VALUE;
for (int i = 1; i < len; i ++) {
max = Math.max(max, prices[i] - min);
min = Math.min(min, prices[i]);
}
return Math.max(max, 0);
}