Java All 3 Solutions (BruteForce-timeout, DP-3ms & Divide&Conquer-4ms)


  • 3
    public class Solution {
        
        public int maxProfitBruteForce(int[] prices) {
            int max = 0;
            for(int i=0; i<prices.length; i++)
                for(int j=i+1; j<prices.length; j++)
                    max = prices[j]-prices[i] > max ? prices[j]-prices[i] : max;
            return max;
        }
        
        public int maxProfitRec(int[] prices, int i, int j) {
            if(i==j)
                return 0;
            int mid = (i+j) / 2;
            int leftProfit = maxProfitRec(prices, i, mid);
            int rightProfit = maxProfitRec(prices, mid+1, j);
            int subMax = Math.max(leftProfit,rightProfit);
            
            int leftMin = prices[i];
            for(int k=i+1; k<=mid; k++)
                leftMin = prices[k] < leftMin ? prices[k] : leftMin;
            
            int rightMax = prices[mid+1];
            for(int k=mid+2; k<=j; k++)
                rightMax = prices[k] > rightMax ? prices[k] : rightMax;
            
            int crossMax = Math.max(0,rightMax-leftMin);
            
            return Math.max(subMax,crossMax);
        }
        
        public int maxProfitDp(int[] prices) {
            int buy = prices[0];
            int max = 0;
            for(int i=1; i<prices.length; i++) {
                max = prices[i]-buy > max ? prices[i]-buy : max;
                if(prices[i]<buy)
                    buy = prices[i];
            }
            return max;
        }
        
        public int maxProfit(int[] prices) {
            if(prices.length==0)
                return 0;
            // return maxProfitBruteForce(prices);
            // return maxProfitRec(prices,0,prices.length-1);
            return maxProfitDp(prices);   
        }
        
    }

Log in to reply
 

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