121. Best Time to Buy and Sell Stock

Version #2 DP / Kadane's Algorithm

99.97 %
class Solution {
    public int maxProfit(int[] prices) {
        // Accumulate difference of price between days
        // Find the maximum subarray of diff array -> Kadane's Algo
        // prices =  [7,1,5,3,6,4]
        // diff  = [0,-6,4,-2,3,-2]
        // dp[i] -> maximum subarray ending at i
        // Standing at current index i, we can choose either use dp[i - 1] or not
        // if (dp[i - 1] > 0, dp[i] += dp[i - 1])
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int dp = 0;
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            int dpCurr = prices[i] - prices[i - 1];
            if (dp > 0) {
                dpCurr += dp;
            }
            dp = dpCurr;
            maxProfit = Math.max(maxProfit, dp);
        }
        return maxProfit;
    }
}



Version #1 Simple solution
一刷
87.92 %
Find the global minimum so far
Time O(n)
Space O(1)
二刷

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int max = 0;
        int prevMin = prices[0];
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prevMin) {
                max = Math.max(max, prices[i] - prevMin);
            } else {
                prevMin = prices[i];
            }
        }
        return max;
    }
}
一刷
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int min = Integer.MAX_VALUE;
        int profit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            int diff = prices[i] - min;
            if (diff > 0) {
                profit = Math.max(profit, diff);
            }
        }
        return profit;
    }
}
二刷
99.97 %
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        int min = Integer.MAX_VALUE;
        int profit = 0;
        for (int price : prices) {
            min = Math.min(min, price);
            if (price > min) {
                profit = Math.max(price - min, profit);
            }
        }
        return profit;
    }
}