an implementation of Divide And Conquer


  • 0
    L

    '''

    public int maxProduct(int[] nums){
        return div(nums, 0, nums.length-1);
    }
    
    private int div(int[] nums, int start, int end){
        if (start>end){
            return Integer.MIN_VALUE;
        }
        if (start==end){
            return nums[start];
        }
        int mid = (start+end)/2;
        int left = div(nums, start, mid-1);
        int right = div(nums, mid+1, end);
        int prd = 1;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int midMax = Integer.MIN_VALUE;
        for (int i=mid;i>=start;i--){
            prd *= nums[i];
            max = Math.max(max, prd);
            min = Math.min(min, prd);
            midMax = Math.max(midMax, max);
        }
        for (int i=mid+1;i<=end;i++){
            int temp = max;
            max = Math.max(nums[i]*max, nums[i]*min);
            min = Math.min(nums[i]*temp, nums[i]*min);
            midMax = Math.max(max, midMax);
        }
        return Math.max(left, Math.max(midMax, right));
    }
    

    '''


Log in to reply
 

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