121. Best Time to Buy and Sell Stock

/**
 * One Pass
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = length of prices array.
 */
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            maxProfit = Math.max(maxProfit, price - minPrice);
        }

        return maxProfit;
    }
}

/**
 * Kadane's Algorithm. This is algorithm can be used if difference array of
 * prices is given.
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(1)
 *
 * N = length of prices array.
 */
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }

        int maxHere = 0;
        int maxSoFar = 0;
        for (int i = 1; i < prices.length; i++) {
            maxHere = Math.max(0, maxHere + prices[i] - prices[i - 1]);
            maxSoFar = Math.max(maxSoFar, maxHere);
        }

        return maxSoFar;
    }
}