Kadane's algorithm
for determining the maximum sum of contiguous subarrays
Unlike the algorithm for determining the maximum sum of subarrays according to the definition of a problem that is slow and has quadratic complexity, Kadane's algorithm is faster because it is linear complexity.
Suppose we have the following array of integers:
{3,5,-10,-34,16 2}
Determining the maximum sums according to Kadan's algorithm would be done as follows:
- It is first loaded or initialize an array, the maximum sum of contiguous subarrays is determined. for example the array previously shown.
- Determine the dimension of the array.
- We have created two maximum sums : one that remembers the current maximum after the end of the iteration of the outer loop and the other is the maximum from the very beginning. We initialize both variables to zero.
- Through the outer loop we move the current position trough the elements of the array from the first to the last.
- For the current position, we create the sum by adding the current member of the array to the previous maximum sum created at the end of iteration.
- Let's compare the maximum we got as the current one, only for positive numbers, at the end of the iteration, with the maximum sum from the beginning. And if it is higher, we update the existing maximum.
- In case we get a negative number for the current maximum, which can happen if the current element of the array is a negative number, and then we set it to zero, because there is always an empty array between the subsets, the sum of which is equal to zero.
- The procedure is repeated until the outer loop is completed.
#include < stdio.h >
#include < stdlib.h >
int main()
{
#include < stdlib.h >
int main()
{
int A[]={ 3,5,-10,-34,16 2};
int n= sizeof(niz)/sizeof(A[0]); //size of array
int MaxCurrent=0; //the current maximum after the end of the iteration of the outer loop
int Max=0; //maximum sum from beginning
/* Through the outer loop we move the current position for the elements of the array from the first to the last */
for(int currentInd=0; currentInd< n; currentInd++)
{
printf("Maximum sum of contiguous arrays is %3d", Max);
return 0;
}int n= sizeof(niz)/sizeof(A[0]); //size of array
int MaxCurrent=0; //the current maximum after the end of the iteration of the outer loop
int Max=0; //maximum sum from beginning
/* Through the outer loop we move the current position for the elements of the array from the first to the last */
for(int currentInd=0; currentInd< n; currentInd++)
{
MaxCurrent=MaxCurrent+A[currentInd]; //We create the sum for the current position
if(MaxCurrent>Max)
}if(MaxCurrent>Max)
Max=MaxCurrent; // if the current maximum is higher after the iterations are completed, the existing maximum is updated
if(MaxCurrent < 0) /* In case we get a negative number for the current maximum, we use the sum of the empty subarray, which is 0 */
MaxCurrent = 0;
MaxCurrent = 0;
printf("Maximum sum of contiguous arrays is %3d", Max);
return 0;