3ms Java Divide-and-Conquer Solution beats 85%


  • 1
    public class Solution {
        
        public int maxProductRec(int[] nums, int i, int j) {
            if(i==j)
                return nums[i];
            int mid = (i+j)/2;
            int leftMax = maxProductRec(nums,i,mid);
            int rightMax = maxProductRec(nums,mid+1,j);
            int subMax = Math.max(leftMax,rightMax);
            
            int leftContiguousMax = nums[mid];
            int leftContiguousMin = nums[mid];
            int leftProduct = nums[mid];
            for(int k=mid-1; k>=i; k--) {
                leftProduct *= nums[k];
                leftContiguousMax = leftProduct > leftContiguousMax ? leftProduct : leftContiguousMax;
                leftContiguousMin = leftProduct < leftContiguousMin ? leftProduct : leftContiguousMin;
            }
            
            int rightContiguousMax = nums[mid+1];
            int rightContiguousMin = nums[mid+1];
            int rightProduct = nums[mid+1];
            for(int k=mid+2; k<=j; k++) {
                rightProduct *= nums[k];
                rightContiguousMax = rightProduct > rightContiguousMax ? rightProduct : rightContiguousMax;
                rightContiguousMin = rightProduct < rightContiguousMin ? rightProduct : rightContiguousMin;
            }
            
            int crossMax = Math.max(leftContiguousMax*rightContiguousMax, leftContiguousMin*rightContiguousMin);
            
            return Math.max(subMax, crossMax);
        }
        
        public int maxProduct(int[] nums) {
            return maxProductRec(nums, 0, nums.length-1);
        }
    }

Log in to reply
 

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