Best Time to Buy and Sell Stock - LeetCode

// Best Time to Buy and Sell Stock - https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

class Solution {
    // Brute Force
    // Time Complexity: O(n^2)
    // Space Complexity: O(1)
    // Below brute force solution leads to Time Limit Exceeded on LeetCode
    // public int maxProfit(int[] prices) {
    //     int maxP = 0;
    //         for(int i = 0; i < prices.length; i++) {
    //             int curMax = 0;
    //             for(int j = i + 1; j < prices.length; j++) {
    //                 int profit = prices[j] - prices[i];
    //                 if(profit > curMax) {
    //                     curMax = profit;
    //                 }
    //             }
    //             maxP = Math.max(maxP, curMax);
    //         }
    //     return maxP;
    // }

    // Two Pointers (Sliding Window)
    // Time Complexity: O(n)
    // Space Complexity: O(1)
    // public int maxProfit(int[] prices) {
        // int maxP = 0;
        // int l = 0, r = 1;
        // while(r < prices.length) {
            // if(prices[l] < prices[r]) {
                // int profit = prices[r] - prices[l];
                // maxP = Math.max(maxP, profit);
            // }
            // else {
                // l = r;
            // }
            // r++;
        // }
        // return maxP;
    // }



    // Dynamic Programming
    // Time Complexity: O(n)
    // Space Complexity: O(1)
    public int maxProfit(int[] prices) {
        int maxP = 0;
        int minSoFar = Integer.MAX_VALUE;
        for(int i = 0; i < prices.length; i++) {
            int curMax = prices[i] - minSoFar;
            maxP = Math.max(maxP, curMax);
            minSoFar = Math.min(minSoFar, prices[i]);
        }
        return maxP;
    }

}