121. Best Time to Buy and Sell Stock

time: O(n)

space: O(1)

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]


*/