In this tutorial, we will see how to solve the maximum sub array sum problem efficiently using the Kadane’s Algorithm.

Maximum subarray sum

What is the maximum subarray sum problem? Say, you’re given an array of integers, of size n, and you’re asked to find the contiguous sub array with maximum sum, how will you do that? More specifically, if you’re asked to find the sum of such contiguous subarray, how will you approach the problem?

Naive approach

The brute force solution involves finding all possible contiguous sub arrays and finding the sum, to find the maximum possible sum. For this, we need to run two loops, one iterating over the array elements to fix the leftmost element of the subarray, and the other loop keeps iterating on the right of this chosen element to fix the rightmost element of the subarray.

What is the time complexity of this approach? Since we’re running two for loops, it’ll take O(n²) time complexity.

Can this be improved? Can this be solved in a single pass?

Kadane’s algorithm

• Iterate over the array and keep track of two variables max_so_far and max_ending_here.
• Initially, both max_so_far and max_ending_here are initialized to zero.
• At index i, max_ending_here computes the subarray with largest sum ending at i, and, max_so_far computes the subarray with the largest sum anywhere in A[0..i].
• Keep updating the two variables at every iteration, and at the end of the pass, max_so_far holds the maximum subarray sum.
• The pseudo code for implementing the above approach :

     Initialize : 
     max_so_far = 0 
     max_ending_here = 0 
     Loop over the elements of the array : 
     At index i, of the array 
      max_ending_here = max_ending_here+arr[i] 
      if(max_ending_here < 0) 
        max_ending_here = 0 
      if(max_ending_here > max_so_far) 
        max_so_far = max_ending_here 
     return max_so_far

Implementation in Python

def maxSubArraySum(a,size):
    (max_so_far, max_ending_here)=(0,0)
    for num in a:
        max_ending_here = max_ending_here+num
        if(max_ending_here > max_so_far):
            max_so_far = max_ending_here
        if(max_ending_here < 0):
            max_ending_here=0
    return max_so_far


if __name__ == "__main__":
  arr = [-2,1,-3,4,-1,2,1,-5,4]
  res = maxSubArraySum(arr,9)
  print("Output : ",res)

Output:  6

Implementation in JAVA

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

public class kadanes
{
  public static void main(String[] args)
  {
    int arr[] = {-2,1,-3,4,-1,2,1,-5,4};
    int n = arr.length;
        	int max_so_far=0, max_ending_here=0;
        	for(int i=0; i<n; i++)
        	{
            		max_ending_here = max_ending_here+arr[i];
            		if(max_ending_here > max_so_far)
                		max_so_far = max_ending_here;
            		if(max_ending_here < 0)
                		max_ending_here = 0;
        	}

    System.out.println(max_so_far);
        
  }
}

Complexity analysis

Since this approach works in a single pass, the time complexity is O(n). It doesn’t utilize any extra memory, and hence, the space complexity is constant, i.e., O(1).

This algorithm uses “optimal substructures” i.e., the maximum subarray ending at each position is computed from the maximum subarray ending at the previous position, and hence, this approach is a simple application of dynamic programming.

References:

• More on Maximum Sub-Array Problem
• Three way Partitioning Problem