Maximum Continuous Sum

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



Leave a Reply

Your email address will not be published. Required fields are marked *