# Maximum Subarray

Two things need to be pay attention to here.

- If all the elements in an array are negative, we have to return the largest one
- If the current sum is negative we need to update it to zero

public int maxSubArray(int[] A) { if(A.length == 0 || A == null){ return 0; } if(A.length == 1){ return A[0]; } int curSum = 0; int max = A[0]; for(int i=0; i<A.length ; i++){ curSum += A[i]; //the order of the following cannot be reversed, otherwise we cannot pass the test cases where // all the numbers are negative if(curSum > max){ max = curSum; } if(curSum < 0){ curSum = 0; } } return max; }

Advertisements

Leave a Comment