C Programming - Max Sum

You have an array of n nonzero numbers. The array is randomly filled with positive and negative numbers.

Write an algorithm/program to find 2 such indexes in the array, so as the sum of the numbers between these indexes is the maximum.

For e.g. if the array is
10, -20, 9, 8, 3, -12, 6, 3, 4, 1, -5, 3, -1
Then the indexes would be 2 and 9, the sum is 9 + 8 + 3 + -12 + 6 + 3 + 4 + 1 =22

At first glance it might look that the correct answer is 2 and 4, the sum is 9 + 8 + 3 =20

And if u r thinking that if we sum up all, then the sum is 10 + -20 + 9 + 8 + 3 + -12 + 6 + 3 + 4 + 1 + -5 + 3 + -1 = 9.

In some cases it might turn out to be the right one, but not always.

Solution:

#define LIST 10, -20, 9, 8, 3, -12, 6, 3, 4, 1, -5, 3, -1

#define LIST -5, -2, -1

#define LIST -5, -2, 0



int main()

{

int nArray[]={LIST};

int nMax,nTempMax,i;

int nStartIndex=0, nStopIndex=0,nSIndex=0;

nMax=nTempMax=nArray[0];

for(i=1;i < sizeof(nArray)/sizeof(int);i++) {

(nTempMax +nArray[i] > 0) ? (nTempMax +=nArray[i]) : (nSIndex= i, nTempMax =nArray[i]);

(nMax < nTempMax ) ? (nMax = nTempMax, nStartIndex = nSIndex, nStopIndex = i) : 0;

}

printf("Start: %d, Stop: %d Max: %d\n",nStartIndex+1,nStopIndex+1,nMax);

}

Labels: C