Cacher is the code snippet organizer for pro developers

/*
2019/11/29
https://www.youtube.com/watch?v=TgnftvU8rxc
1. find the current min price
2. find max profit based on step 1
3. if there is a lower min price, replace it with the new min price
4. repeat step 2

Complexity Analysis

Time complexity : O(n)O(n). Only a single pass is needed.

Space complexity : O(1)O(1). Only two variables are used.

*/

class Solution {
  public int maxProfit(int[] prices) {
    int curMinPrice = Integer.MAX_VALUE;
    int maxProfit = 0;
    for( int i = 0; i<prices.length; i++){
      if(prices[i]<curMinPrice){
        curMinPrice = prices[i];
      }
      else if(prices[i]-curMinPrice > maxProfit){
        maxProfit =prices[i]-curMinPrice;
      }
    }
    return maxProfit;
  }
}