Kadane’s Algorithm for Maximum Sum Subarray

Write an efficient program to find the sum of subarray (Not subsequence) within a 1-D array of numbers that has the largest sum out of all other combinations.

Naïve approach to this problem would be to maintain a variable to account for the maximum sum, and iterate the array with a nested loop. This would take O(N²) time to iterate throughout the array.

Kadane’s Algorithm:

The basic idea of Kadane’s Algorithm is to create two variables, one to store the maximum sum so far, and the other to check for the sum till the specific index. Whenever we get the sum till the index greater than the maximum sum so far, we update the maximum sum so far, and in case, sum till the index becomes < 0, we initialize sum till index as 0, because, there is not point in starting a range of subarray with negative numbers at the beginning.

Let us understand it with a pseudo code and a dry run of the program,

Initialize Variables:
max_sum_so_far = INT_MIN
max_sum_ending_here = 0
Loop for each element of the input array:
Inside the loop, handle the conditions below,
1. max_sum_ending_here = max_sum_ending_here + a[i]
2. If (max_sum_so_far < max_sum_ending_here)
max_sum_so_far = max_sum_ending_here
3. If (max_sum_ending_here < 0)
max_sum_ending_here = 0
return max_sum_so_far

Dry Run:

Let’s take the example:
    {-4, -6, 8, -2, -4, 2, 10, -6}

    max_sum_so_far = INT_MIN
    max_sum_ending_here = 0

    for i=0, a[0] = -4
    max_sum_ending_here = max_sum_ending_here + (-4)
    Set max_sum_ending_here = 0 because max_sum_ending_here < 0
    and set max_sum_so_far = -4

    for i=1, a[1] =  -6
    max_sum_ending_here = max_sum_ending_here + (-6)
    Since max_sum_ending_here = -6 and max_sum_so_far = -4, max_sum_so_far will remain -4
    Set max_sum_ending_here = 0 because max_sum_ending_here < 0
      
    
    for i=2, a[2] =  8
    max_sum_ending_here = max_sum_ending_here + (8)
    max_sum_ending_here = 8
    max_sum_so_far is updated to 8 because max_sum_ending_here greater 
    than max_sum_so_far which was -4 till now

    for i=3, a[3] =  -2
    max_sum_ending_here = max_sum_ending_here + (-2)
    max_sum_ending_here = 6

    for i=4, a[4] =  -4
    max_sum_ending_here = max_sum_ending_here + (-4)
    max_sum_ending_here = 2

    for i=5, a[5] =  2
    max_sum_ending_here = max_sum_ending_here + (2)
    max_sum_ending_here = 4

    for i=6, a[6] =  10
    max_sum_ending_here = max_sum_ending_here + (10)
    max_sum_ending_here = 14
    max_sum_so_far is updated to 14 because max_sum_ending_here is 
    greater than max_sum_so_far

    for i=7, a[7] =  -6
    max_sum_ending_here = max_sum_ending_here + (-6)
    max_sum_ending_here = 8

Finally, after the loop terminates, the variables 
max_sum_so_far = 14
max_sum_ending_here = 8
Hence, the final answer returned would be 14

The pseudo code above works only when there is at least one positive integer in the input array. In case of all negative numbers, the code would return the element at index 0.

In C++:

// C++ program to print largest contiguous array sum
#include<iostream>
#include<climits>
using namespace std;

int maxSubArraySum(int a[], int size)
{
	int max_so_far = INT_MIN, max_ending_here = 0;

	for (int i = 0; i < size; i++)
	{
		max_ending_here = max_ending_here + a[i];
		if (max_so_far < max_ending_here)
			max_so_far = max_ending_here;

		if (max_ending_here < 0)
			max_ending_here = 0;
	}
	return max_so_far;
}

/*Driver program to test maxSubArraySum*/
int main()
{
	int a[] = {-4, -6, 8, -2, -4, 2, 10, -6};
	int n = sizeof(a)/sizeof(a[0]);
	int max_sum = maxSubArraySum(a, n);
	cout << "Maximum contiguous sum is " << max_sum;
	return 0;
}

In Java:

import java.io.*;
// Java program to print largest contiguous array sum
import java.util.*;

class Kadane
{
	public static void main (String[] args)
	{
		int [] a = {-2, -3, 4, -1, -2, 1, 5, -3};
		System.out.println("Maximum contiguous sum is " +
									maxSubArraySum(a));
	}

	static int maxSubArraySum(int a[])
	{
		int size = a.length;
		int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

		for (int i = 0; i < size; i++)
		{
			max_ending_here = max_ending_here + a[i];
			if (max_so_far < max_ending_here)
				max_so_far = max_ending_here;
			if (max_ending_here < 0)
				max_ending_here = 0;
		}
		return max_so_far;
	}
}

Output:

Maximum contiguous sum is 14

Time Complexity would be O(N) and Auxiliary Space requirement is O(1).

We can also maintain the indices of the subarray by creating the variables to store the indices whenever we get the maximum sum.

Another implementation of Kadane’s algorithm is to use Dynamic Programming. The space and time complexity would remain same for DP based implementation, but the case when all numbers are negative would be handled correctly.

We can also use a flag and a variable to store the maximum negative integer to handle the case when there are all negative integers in the array. This would not affect time complexity of the program.

Iterative implementation of Kadane’s Algorithm for handling the case when there is no positive integer in the array.

import java.util.*;
import java.io.*;

public class ProgramJava {

    static int maxSubArraySum(int a[]) {
        int size = a.length;
        int negativesCount = 0;
        boolean flag = false;
        int maxNegative = Integer.MIN_VALUE;
        int max_so_far = Integer.MIN_VALUE, max_ending_here = 0;

        for (int i = 0; i < size; i++) {
            max_ending_here = max_ending_here + a[i];
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
            if (max_ending_here < 0)
                max_ending_here = 0;
            if (a[i] < 0) {
                negativesCount++;
                maxNegative = Math.max(maxNegative, a[i]);
            }
        }

        if (negativesCount == size) flag = true;

        if (flag) return maxNegative;
        else return max_so_far;
    }

    public static void main(String[] args) throws IOException {

        int[] arr = {-8, -2, -3, -4, -7};
        int n = arr.length;

        System.out.println(maxSubArraySum(arr));
        
    }
}

Output:

-2

Time Complexity: O(N)

Space Complexity: O(1)