Today we're going to take a look at one of the algorithms that people study when they start learning about dynamic programming. Kadane's algorithm will return the largest sum of individual elements in any contiguous subarray of the array you feed into it, and it'll do it with a runtime of O(n).
Let's take this array as an example:
int arr[9] = {-2,1,-3,4,-1,2,1,-5,4};
First thing that comes to mind when trying to solve this problem is to iterate through every single possible subarray and see which one will give you the largest sum of all individual values contained within this subarray. We could do it using nested for loops and this approach would look a little something like this:
You'd of course would want to keep some sort of a variable to keep track of the highest sum and eventually you'd arrive at the answer, which is 6. Let's now rearrange the order of execution a bit and see if we could improve it a bit:
Notice that here you don't actually have to recalculate all the subarrays that you've already calculated, as long as you keep track of the highest sum of all arrays up until now. In fact, you could take only the current index and then compare it with the sum of itself and the largest sum of the previous lot:
max(current_index, (current_index + largest_sum_of_the_previous_lot));
It may be easier to conceptualise it by looking at a step by step breakdown:
The largest sum is still 6 which is correct. Here is how you could code it in C++:
#include <iostream>
#include <cmath>
using namespace std;
int kadanesAlgorithm(int arr[], int size)
{
int kadane_array[100];
kadane_array[0] = arr[0];
int current_max = arr[0];
for (int i = 1; i <= size; i++)
{
kadane_array[i] = max(arr[i], (arr[i] + kadane_array[i - 1]));
current_max = max(current_max, kadane_array[i]);
std::cout << kadane_array[i-1] << std::endl;
}
return current_max;
}
int main()
{
int arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
int size = sizeof(arr) / sizeof(arr[0]);
int maxSum = kadanesAlgorithm(arr, size);
std::cout << maxSum << std::endl;
return 0;
}
And here is the algorithm and what it does setp by step (pseudo code):
1) Index 0
//Here we're just initializing the parameters with the first element of the array arr[]:
arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
kadane_array[] = { -2 };
current_max=-2;
2) Index 1
arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
current_index=1;
//This is the local max. You don't need to calculate the previous biggest sum again, so we're just going to check if that sum with the current index added to it is greater than just the index alone. Turns out the index itself is greater therefore the largest array for elements up to that index must equal the index itself:
current_local_max=max(previous_local_max+current index, current_index)=max(-2+1, 1) = 1;
//Here we're inputting the local max to the kadane's array which keeps track of local maximums:
kadane_array[] = { -2,1 };
//Here we're just checking the largest sum so far by comparing the current max and the local max at the current index:
current_max=max(current_max, current_local_max)=max(-2,1)=1;
3) Index 2
arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
current_index=-3;
current_local_max=max(previous_local_max+current index, current_index)=max(1+(-3), -3) = -2;
kadane_array[] = { -2,1,-2 };
current_max=max(current_max, current_local_max)=max(1,-2)=1;
4) Index 3
arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
current_index=4;
current_local_max=max(previous_local_max+current index, current_index)=max(-2+4, 4) = 4;
kadane_array[] = { -2,1,-2, 4 };
current_max=max(current_max, current_local_max)=(1, 4) = 4;
5) Index 4
arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
current_index=-1;
current_local_max=max(previous_local_max+current index, current_index)=max(4+(-1), -1) = 3;
kadane_array[] = { -2,1,-2, 4, 3 };
current_max=max(current_max, current_local_max)=(4, 3) = 4;
6) Index 5
arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
current_index=2;
current_local_max=max(previous_local_max+current index, current_index)=max(3+2, 2) = 5;
kadane_array[] = { -2,1,-2, 4, 3, 5 };
current_max=max(current_max, current_local_max)=(4, 5) = 5;
7) Index 6
arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
current_index=1;
current_local_max=max(previous_local_max+current index, current_index)=max(5+1, 1) = 6;
kadane_array[] = { -2,1,-2, 4, 3, 5, 6 };
current_max=max(current_max, current_local_max)=max(5, 6) = 6;
8) Index 7
arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
current_index=-5;
current_local_max=max(previous_local_max+current index, current_index)=max(6+(-5), -5) = 1;
kadane_array[] = { -2,1,-2, 4, 3, 5, 6, 1 };
current_max=max(current_max, current_local_max)=current_max=max(6, 1) = 6;
9) Index 8
arr[] = { -2,1,-3,4,-1,2,1,-5,4 };
current_index=4;
current_local_max=max(previous_local_max+current index, current_index)=max(1+4, 4) = 5;
kadane_array[] = { -2,1,-2, 4, 3, 5, 6, 1, 5 };
current_max=max(current_max, current_local_max)=current_max=max(6, 5) = 6;
Hope it made it clear for you- let me know if you have any questions. Cheers!
HYPER!locrian
