Skip to content

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;
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: