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.
1 public class Solution { 2 public int maxSubArray(int[] A) { 3 if(A.length<=0) return 0; 4 int max = Integer.MIN_VALUE; 5 int sum = 0; 6 for(int i=0;i<A.length;i++){ 7 sum +=A[i]; 8 if(sum>max){ 9 max = sum; 10 } 11 if(sum<0){ 12 sum = 0; 13 } 14 } 15 return max; 16 } 17 }