Baoqiang Cao's Blog

Problem: Given an array of integers, each element can be positive, zero or negative, find a sum of a segment of the elements in the array so that its value is the maximum.

For example, {3, -1, 4, -10,5}, the result should be:

maxsum=6 <= 3-1+4.

Solution:
There are two conditions on the unsorted integer array, one is the sum should be maximum and the other is the sum should be among all consecutive elements. Naturally, there are some segments of elements that their sum are larger than others, so we need be able to find where to stop and start the segment so that its sum is maximum. So we need two variables to store segment sum values for comparison, when we move along the array, one variable store the maximum for current segment, and the other is the maximum so far along the array. And when moving along the array, we also need a flag to tell us whether it is time to compare the current maximum against the maximum so far. Now comes to the key question, when to stop and start?

When to stop?
We start with the first element, if it is non-negative, we for sure keep it in the sum, but otherwise, we need make a decision to either “foresee” it or stop here. “Foresee” here means, when its next is so positive that, a[0]+a[1] is non-negative, so we will overall better off with such a negative element in “longer” term. If a[0]+a[1] is negative, we’ll have no choice but stop the current sum. We can easily derive that this stop rule is a general rule applying for starting at any position.

When to start new segment?
After the stop, we need a new start. We obviously want to start with a positive element because for sure it is contributing positively to the new sum. And after the new start, we follow the stop rule described above. When this new segment is stop, we compare the new sum against the previous sum on previous segment and keep the larger one. Later we just keep the largest sum and compare any new max against it, doing so we’ll get the max for the whole array.

The following is my implementation in C/C++:

#include <iostream>
using namespace std;
int sumMax(int *a, int n) {
	if(n==0){
		cout << "Error: the array is empty!\n";
	}
	int max1, max2;
	int flag=-1;
	int k=n;
	max1=max2=0;
	while(k>0) {
		if(*a >= 0) {
			if(flag==1) {
				max2+=(*a);
			} else {
				max1+=(*a);
			}
			a++;k--;
		} else {
			if(k-1>0) {
				if(*a+*(a+1)>=0){
					if(flag==1) {
						max2+=(*a+*(a+1));
					} else {
						max1+=(*a+*(a+1));
					}
					a+=2;k-=2;
				} else {
					flag=1;
					a++;k--;
					if(*a >=0) {
						max2=(*a);a++;k--;
					}
				}
			}
		}
		if(max2>=max1) {
			max1=max2;
			flag=-1;
		}
	}
	return max1;
}

int main(void) {
	int a[]={4, -1, 3, -10, 1, 25, -11, 30, -10, 50};
	int i;
	int max=sumMax(a,10);
	for(i=0; i<10; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
	cout << "max=" << max << endl;
	return 1;
}