Largest sum contiguous subarry

Find sum of contiguous subarray, which is maximum.

For input { -2, -3, 4, -1, -2, 1, 5, -3 }, Maximum value is 7 starting at index 2 end at 6.

I just implemented Kadane’s algorithm. Go through following wiki article for more information.

https://en.wikipedia.org/wiki/Maximum_subarray_problem

import java.util.Objects;

public class MaxSubSequence {

 public static String maxSubSequence(int arr[]) {
  Objects.nonNull(arr);

  int maximum_so_far = arr[0];
  int max = arr[0];
  int endIndex = 0, count = 0, indexDiff = 0;

  for (int i = 1; i < arr.length; i++) {
   if (maximum_so_far > 0) {
    maximum_so_far = maximum_so_far + arr[i];
    count++;
   } else {
    maximum_so_far = arr[i];
    count = 0;
   }

   if (maximum_so_far > max) {
    max = maximum_so_far;
    endIndex = i;
    indexDiff = count;
   }
  }

  return "Maximum value is " + max + " starting at "
    + (endIndex - indexDiff) + " end at " + endIndex;
 }
}

public class MaxSubSequenceTest {

 public static void main(String args[]) {
  int arr1[] = { -2, -3, 4, -1, -2, 1, 5, -3 };
  int arr2[] = { -2, -3, -4, -1, -2, -1, -5, -3 };
  int arr3[] = { -2, -3, 4, -1, -2, 1, 5, -3, -30, 25 };
  int arr4[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

  System.out.println(MaxSubSequence.maxSubSequence(arr1));
  System.out.println(MaxSubSequence.maxSubSequence(arr2));
  System.out.println(MaxSubSequence.maxSubSequence(arr3));
  System.out.println(MaxSubSequence.maxSubSequence(arr4));
 }
}

Output

Maximum value is 7 starting at 2 end at 6
Maximum value is -1 starting at 3 end at 3
Maximum value is 25 starting at 9 end at 9
Maximum value is 7 starting at 2 end at 6