I have look up online and derived a divide and conquer method from others' solution but still time out.


  • 1
    U
    public class Solution {
        public int maxSubArray(int[] nums) {
            if(nums.length == 0 || nums == null) {
                return 0;
            } 
            
            int ans = findMax(nums, 0, nums.length - 1);
            
            return ans;
        }
        
        public int findMax(int[] nums, int left, int right) {
            if(left < right) {
                int mid = left + (right - left) / 2;
                int leftMax = findMax(nums, left, mid);
                int rightMax = findMax(nums, mid + 1, right);
                int leftHalf = Integer.MIN_VALUE, rightHalf = Integer.MIN_VALUE;
                
                int leftSum = 0;
                for(int i = mid; i > 0; i--) {
                    leftSum = leftSum + nums[i];
                    leftHalf = leftHalf >= leftSum ? leftHalf : leftSum;
                }
                
                int rightSum = 0;
                for(int i = mid + 1; i < nums.length; i++) {
                    rightSum += nums[i];
                    rightHalf = rightHalf >= rightSum ? rightHalf : rightHalf;
                }
                
                int tmpRes = Math.max(leftMax, rightMax);
                int res = Math.max(tmpRes, leftHalf + rightHalf);
                
                return res;
            } else {
                return nums[left];
            }
        }
    }

  • 0

    Please try submitting again, the divide and conquer solution for Java should be accepted now.


Log in to reply
 

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