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
andmax_ending_here
. - Initially, both
max_so_far
andmax_ending_here
are initialized to zero. - At index
i
,max_ending_here
computes the subarray with largest sum ending ati
, and,max_so_far
computes the subarray with the largest sum anywhere inA[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.