sharing my 2ms JAVA solution..


  • 0
    D
    public class Solution {
        public int maxProfit(int[] prices) {
            int n = prices.length;
            if (n<2) return 0;
            int[] left = new int[n];
            int[] right = new int [n];
            int min = prices[0];
            for (int i=1; i<n; i++) {
                min = Math.min(min, prices[i]);
                left[i] = Math.max(left[i-1], prices[i]-min);
            }
            int max = prices[n-1];
            for (int i=n-2; i>=0; i--) {
                max = Math.max(max, prices[i]);
                right[i] = Math.max(right[i+1], max-prices[i]);
            }
            int result = 0;
            for (int i=0; i<n; i++) result = Math.max(result, left[i]+right[i]);
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.