© Parineeth M R
Question 54. Find the maximum continuous sum in an array
An array can have positive and negative elements in it. We have to find a subset of contiguous elements in the array whose sum is the maximum. Let the maximum continuous sum be represented as MCS
In the brute force approach, we pick an element and then go on adding its right neighbors one by one to find the maximum contiguous sum starting at that element. We then repeat the process for all elements in the array to find the MCS across all elements. The time complexity of the brute force approach is O(n2).
However it is possible to find the MCS in O(n) time using kadane’s algorithm. This algorithm works for all cases (including the case where all the elements are negative). We maintain the variable max_local which will store the sum of the neighboring elements in the current window. The algorithm is described below:
1. Choose the first element and initialize max_local to the first element.
2. Traverse through the remaining elements. If the result of adding max_local to the current element is greater than current element, then add the current element to max_local and keep continuing the window. If however the result of adding max_local to the current element is less than the current element, then start a fresh window that starts at the current element and initialize max_local to the current element.
3. The maximum value of max_local across all elements will be the MCS of the array.
Let A = {4, -9, 5, 6 , 1} . max_local is initialized to 4. The remaining calculations are shown in the table below
C/C++
/*
a: the array of numbers for which the MCS should be found,
length: number of elements. Should >= 1
mcs_start_pos: the starting array index of the MCS is returned here
mcs_end_pos: the ending array index of the MCS is returned here
Return value: Maximum continous sum of the elements
*/
int kadane_mcs(int a[], int length, int *mcs_start_pos, int *mcs_end_pos) {
int i, max_local, max_global;
int cur_start_pos;
*mcs_start_pos = *mcs_end_pos = 0;
cur_start_pos = 0; /*store the start position of the current window*/
max_local = max_global = a[0];
/*Traverse from the second element onwards*/
for (i = 1; i < length; ++i) {
max_local = max(a[i], a[i] + max_local);
if (max_local == a[i])
cur_start_pos = i; /*start a new window here*/
/*Find the global maximum*/
if (max_local > max_global) {
max_global = max_local;
*mcs_start_pos = cur_start_pos;
*mcs_end_pos = i;
}
}
return max_global;
}
Java
/* a: array of numbers for which MCS should be found.
At least 1 element should be present
mcsStartPos: the starting array index of the MCS is returned here
mcsEndPos: the ending array index of the MCS is returned here
Return value: Maximum continous sum of the elements
*/
public static int kadaneMcs(int[] a, Int mcsStartPos, Int mcsEndPos) {
int length = a.length;
int curStartPos = 0; /*store the start position of the current window*/
int maxLocal = a[0], maxGlobal = a[0];
mcsStartPos.value = mcsEndPos.value = 0;
/*Traverse from the second element onwards*/
for (int i = 1; i < length; ++i) {
maxLocal = Math.max(a[i], a[i] + maxLocal);
if (maxLocal == a[i])
curStartPos = i;/*start a new window here*/
/*Find the global maximum*/
if (maxLocal > maxGlobal) {
maxGlobal = maxLocal;
mcsStartPos.value = curStartPos;
mcsEndPos.value = i;
}
}
return maxGlobal;
}
Python
#a: list of numbers for which MCS should be found. size of a >= 1 #Return value: 1. Maximum continuous sum of the elements , # 2. the starting list index of the MCS # 3. the ending list index of the MCS def kadane_mcs(a) : length = len(a) mcs_start_pos = mcs_end_pos = 0 cur_start_pos = 0 #store the start position of the current window max_local = max_global = a[0] #Traverse from the second element onwards for i in range(1, length): max_local = max(a[i], a[i] + max_local) if (max_local == a[i]): cur_start_pos = i #start a new window here #Find the global maximum if (max_local > max_global) : max_global = max_local mcs_start_pos = cur_start_pos mcs_end_pos = i return max_global, mcs_start_pos, mcs_end_pos