Maximum Subarray Sum: Kadane's algorithm

Kadane's algorithm

Kadane's algorithm consists of a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position.

Usage of Kadane's algorithm         

It is used to obtain the maximum subarray sum from an array of integers.

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

Code in Java:

import java.util.Scanner;

/* Class kadane */

public class KadaneAlgorithm {

      /* Function to largest continuous sum */

      public static intmaxSequenceSum(int[] arr) {       

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

            for (inti= 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