My Java solution


  • -1

    The O(n) solution is simple. We use a variable(here is sum) to save the subarray sum. When sum is less then 0, that is say the subarray sum before is no good to the maximum subarray sum, so we need set it to 0.

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

    the divide and conquer approach is nO(logn)

    public static int maxSubArray(int[] nums) {
    	return maxSubArray(nums, 0, nums.length - 1);    
    }
    public static int maxSubArray(int[] nums, int left, int right) {
    	if (left > right) {
    		return Integer.MIN_VALUE;
    	} else if (left == right) {
    		return nums[left];
    	} else {
    		int middle = (right - left) / 2 + left;
    		int leftMax = maxSubArray(nums, left, middle);
    		int rightMax = maxSubArray(nums, middle + 1, right);
    		int sum = 0;
    		int maxToLeft = Integer.MIN_VALUE;
    		for (int i = middle; i >= left; i--) {
    			sum += nums[i];
    			maxToLeft = Math.max(maxToLeft, sum);
    		}
    		sum = 0;
    		int maxToRight = Integer.MIN_VALUE;
    		for (int i = middle + 1; i <= right; i++) {
    			sum += nums[i];
    			maxToRight = Math.max(maxToRight, sum);
    		}
    		int result = maxToLeft + maxToRight;
    		result = Math.max(result, leftMax);
    		result = Math.max(result, rightMax);
    		return result;
    	}
    }

Log in to reply
 

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