## Thursday, 12 January 2017

### Maximum Subarray Sum: 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.

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;

/* Function to largest continuous sum */
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};