2.5 Maximum Subarray

Description

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Method

since it requires contiguous, it means that for each element, it has two situations that are in the subarray or not. so how to decide whether it is in or not. if the sum of previous subarray is negative, it means that it need has a new start.

and each time when we has a new subarray we should update the global var which stand of the max sum of subarray.

Time and Space Complexity

O(n)

Code

public class Solution {

public int maxSubArray(int[] nums) {
       if (nums == null || nums.length == 0){
           return 0;
       }
       int max = Integer.MIN_VALUE;
       int sum = 0;
       for (int i = 0; i < nums.length; i++){
           if (sum < 0){
               sum = nums[i];
           } else {
               sum += nums[i];
           }
           max = Math.max(sum, max);
       }
       return max;
}

}