Maximum Subarray Problem is a famous problem in dynamic programming. The algorithm we use to solve this problem is known as Kadane’s algorithm. It is a slightly tricky algorithm to understand but don’t you worry. This tutorial we go over the algorithm in an easy to understand manner.
What is the Maximum Subarray Problem?
This problem requires you to find the largest possible sum of a contiguous subarray, within a given one-dimensional array A[1…n] of numbers.
The array will contain negative integers. If the array only contains positive integers then the answer will be the sum of the complete array.
Kadane’s Algorithm
The Kadane’s Algorithm solves this problem by traversing over the entire array and keeping two variables to track the sum so far and overall maximum.
The conditions under which each of the two variables are updated are important.
Let’s look at the algorithm :
- Initialize max_so_far = 0
- Initialize max_ending_here = 0
- Repeat steps 4 to 6 for each element of the array
- set max_ending_here = max_ending_here + a[i]
- if(max_ending_here < 0) then set max_ending_here = 0
- if(max_so_far < max_ending_here) then set max_so_far = max_ending_here
- return max_so_far
That’s Kadane’s algorithm in six seven easy steps.
We can summarize the update criteria in two sentences :
When the variable max_ending_here becomes negative, we set it to zero. At each iteration, we check for max_so_far < max_ending_here, if the condition is true then we update max_so_far.
The for loop for steps 4 to 6 will be :
|
1 2 3 4 5 6 7 8 |
for (int i = 0; i < length; i++) { max_ending_here = max_ending_here + arr[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; } |
Example
Let’s look at an example :
The maximum subarray is from i=2 to i=6. The maximum sum is 7.
Kadane’s algorithm Implementation
The complete code for Kadane’s algorithm is as follows, in the code we have printed the values of max_so_far and max_ending_here at each step.
1. Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
package com.JournalDev; public class Main { static int maxSubArraySum(int arr[]) { // initializing variables int length = arr.length; int max_so_far = 0, max_ending_here = 0; // for loop step 4 to 6 for (int i = 0; i < length; i++) { max_ending_here = max_ending_here + arr[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; System.out.println("For i = "+i); System.out.println("Max_ending_here = "+max_ending_here); System.out.println("Max_so_far = "+max_so_far); System.out.println(); } //return max_so_far as the answer return max_so_far; } public static void main(String[] arg) { int [] arr = {-2, -3, 4, -1, -2, 1, 5, -3}; System.out.println("Maximum sum is " + maxSubArraySum(arr)); } } |
2. C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include<iostream> #include<climits> using namespace std; int maxSubArraySum(int arr[], int length) { // initializing variables int max_so_far = 0, max_ending_here = 0; // for loop step 4 to 6 for (int i = 0; i < length; i++) { max_ending_here = max_ending_here + arr[i]; if (max_so_far < max_ending_here) max_so_far = max_ending_here; if (max_ending_here < 0) max_ending_here = 0; cout << "For i = " << i; cout << "Max_ending_here = " << max_ending_here; cout << "Max_so_far = " << max_so_far ; } return max_so_far; } int main() { int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}; int n = sizeof(arr)/sizeof(arr[0]); int max_sum = maxSubArraySum(arr, n); cout << "Maximum contiguous sum is " << max_sum; return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
Output : For i = 0 Max_ending_here = 0 Max_so_far = 0 For i = 1 Max_ending_here = 0 Max_so_far = 0 For i = 2 Max_ending_here = 4 Max_so_far = 4 For i = 3 Max_ending_here = 3 Max_so_far = 4 For i = 4 Max_ending_here = 1 Max_so_far = 4 For i = 5 Max_ending_here = 2 Max_so_far = 4 For i = 6 Max_ending_here = 7 Max_so_far = 7 For i = 7 Max_ending_here = 4 Max_so_far = 7 Maximum sum is 7 |
Conclusion
This tutorial was about Kadane’s algorithm. If you’re interested in more problems like this, you should check our tutorial on subset sum problem.