Find max subarray sum using Kadane's algorithm

Maximum subarray sum of an integer array

Kadane's algorithm

• Scan through the array values
• Computing at each position the maximum (positive sum) subarray ending at that position

Pseudo code

Initialize: 

  max_so_far = 0

  max_ending_here = 0

Loop for each element of the array

     max_ending_here = max_ending_here + a[i]

     if(max_ending_here < 0)

          max_ending_here = 0

     if(max_so_far < max_ending_here)

          max_so_far = max_ending_here

return max_so_far

Java code

public class KadaneAlgorithm {

      public static int maxSequenceSum(int[] arr) {       

            int maxSoFar = arr[0], maxEndingHere = arr[0];

            for (int i = 1; i < arr.length; i++) {

                  /* calculate maxEndingHere */

                  if (maxEndingHere < 0) {

                        maxEndingHere = arr[i];

                  } else {

                        maxEndingHere += arr[i];

                  }

                  /* calculate maxSoFar */

                  if (maxEndingHere >= maxSoFar) {

                        maxSoFar = maxEndingHere;

                  }

            }

            return maxSoFar;

      }

      public static void main (String[] args) {

            int[] arr = {8,6,5,-19,-24,2,8,9,14,-1,7};

            int sum = KadaneAlgorithm.maxSequenceSum(arr);

            System.out.println("Maximum Sequence sum is: "+ sum);

      }

}

Output: Maximum Sequence sum is: 39