Skip to content

Maximum Subarray

11/18/2013

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: