Maximum Subarray

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.

01 public int maxSubArray(int[] A) {
02     int sum=0;
03     int maxSum=A[0];
04     for(int i=0;i<A.length;i++)      
05     {
06         sum+=A[i];
07         if(sum>maxSum)
08         {
09             maxSum=sum;
10         }
11         if(sum<0)
12         {
13             sum=0;
14         }
15     }
16     return maxSum;
17 }