Java Solution #dp


  • 2
    public class Solution {
        public int maxProfit(int[] prices) {
            
            // guard
            if (prices.length == 0) return 0;
            
            int left[] = new int[prices.length];
            int right[] = new int[prices.length];
            
            // max profit for a transaction on the left
            int min = prices[0];
            int maxProfitL = 0;
            for (int i=0; i<prices.length; ++i) {
                min = Math.min(min, prices[i]);
                maxProfitL = Math.max(maxProfitL, prices[i] - min);
                left[i] = maxProfitL;
            }
            
            // max profit for a transaction on the right
            int max = prices[prices.length-1];
            int maxProfitR = 0;
            for (int i=prices.length-1; i>0; --i) {
                max = Math.max(max, prices[i]);
                maxProfitR = Math.max(maxProfitR, max - prices[i]);
                right[i] = maxProfitR;
            }
            
            // max profit on both side
            int maxProfit = 0;
            for (int i=0; i<prices.length; ++i) {
                maxProfit = Math.max(maxProfit, left[i] + right[i]);
            }
            
            return maxProfit;
        }
    }
    

Log in to reply
 

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