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.

Code In JAVA:

Version 1:
    public int maxSubArray(int[] A) {
      int max = Integer.MIN_VALUE;
      int sum = 0;
      if (A.length == 0 || A == null) {
         return 0;
      }
      // if sum > 0, then keep on going, else < 0, then reset sum to 0
      for (int i = 0; i < A.length; i++) {
         sum += A[i];
         max = Math.max(max, sum);
         sum = Math.max(sum, 0);
      }
      return max;
   }