O(n) and Divide and Conquer solutions


  • 0
    A

    O(n) solution :

    public int maxSubArray(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }
    
            int maxSum = nums[0], currentSum = nums[0];
            for (int i = 1; i < nums.length; i++) {
                 currentSum = Math.max(nums[i], currentSum + nums[i]);
                 maxSum = Math.max(maxSum, currentSum);
            }
    
            return maxSum;
        }
    

    Divide and conquer solution :

        public int maxSubArray(final int[] nums) {
            return maxSubArrayDivideAndConquerHelper(nums, 0, nums.length - 1);
        }
    
        private int maxSubArrayDivideAndConquerHelper(final int[] nums, final int start, final int end) {
            if (start < end) {
                int mid = start + (end - start)/2;
                int leftMaxSum = maxSubArrayDivideAndConquerHelper(nums, start, mid);
                int rightMaxSum = maxSubArrayDivideAndConquerHelper(nums, mid+1, end);
                int crossingMaxSum = maxCrossingSubArraySum(nums, start, end, mid);
    
                if (leftMaxSum >= rightMaxSum && leftMaxSum >= crossingMaxSum) {
                    return leftMaxSum;
                } else if (rightMaxSum >= leftMaxSum && rightMaxSum >= crossingMaxSum) {
                    return rightMaxSum;
                } else {
                    return crossingMaxSum;
                }
            } else {
                return nums[start];
            }
        }
    
        private int maxCrossingSubArraySum(final int[] nums, final int start, final int end, final int mid) {
            int leftMaxSum = Integer.MIN_VALUE;
            int sum = 0;
            for (int i = mid; i >= start; i--) {
                sum += nums[i];
                if (sum > leftMaxSum) {
                    leftMaxSum = sum;
                }
            }
            
            int rightMaxSum = Integer.MIN_VALUE;
            sum = 0;
            for (int i = mid + 1; i <= end; i++) {
                sum += nums[i];
                if (sum > rightMaxSum) {
                    rightMaxSum = sum;
                }
            }
            
            return leftMaxSum + rightMaxSum;
        }
    

Log in to reply
 

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