hint: need to find the largest peak following the smallest valley
keep the min price, and find maxprofit
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
int min = Integer.MAX_VALUE;
for (int price : prices) {
if (price < min) {
min = price;
}
if (price - min > profit) {
profit = price - min;
}
}
return profit;
}
}
class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int result = 0;
for (int price : prices) {
min = Math.min(min, price);
result = Math.max(result, price - min);
}
return result;
}
}
/*
if do 2 pass like
find min first => get 1 and index is 2
this case will be failed, because miniest one at the last, in this case will fail
[2,4,1]
in this case; should be 2
but in this case it's ok
[7,1,5,3,6,4]
so we should just find min value until current, we only care about the min value until current element, and cal the profit
ex:
to index 2, value: 5, the min is 1, so the profit is 5-1 = 4
^
[7,1,5,3,6,4]
ex:
o index 1, value: 4, the min is 2, so the profit is 4-2 = 2
^
[2,4,1]
o index 2, value: 1, the min is 1, so the profit is 1-1 = 0 (2 wins!)
^
[2,4,1]
*/