O(n) O(1)
Intuition
At each day, the best profit if we sell today is today - minSoFar. Track
minSoFar as we scan and maintain the global max of that difference.
Explanation
Walk-through
prices = [7,1,5,3,6,4]
| i | price | min | profit = price - min | best |
|---|---|---|---|---|
| 0 | 7 | 7 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
| 2 | 5 | 1 | 4 | 4 |
| 3 | 3 | 1 | 2 | 4 |
| 4 | 6 | 1 | 5 | 5 |
| 5 | 4 | 1 | 3 | 5 |
Implementation
class Solution {
public int maxProfit(int[] prices) {
int minSoFar = Integer.MAX_VALUE;
int best = 0;
for (int p : prices) {
if (p < minSoFar) {
minSoFar = p;
} else {
best = Math.max(best, p - minSoFar);
}
}
return best;
}
}