Related Blog Items

• Printing array spirally - c program
• Printing array spirally - recursive routine
• Different signature problem with extern variables
• Questions asked in various job interviews (in Programming)
• C++ Basics Tutorial - Lesson 4

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);

}

[tags] Max Sum between two array indexes,max sum program,max sum source code[/tags]

Popularity: 4%

You need to log on to convert this article into PDF

Related Blog Items

• Printing array spirally - c program
• Printing array spirally - recursive routine
• Different signature problem with extern variables
• Questions asked in various job interviews (in Programming)
• C++ Basics Tutorial - Lesson 4

This entry was written by ponnada and posted on December 22, 2006 at 12:49 pm and filed under C Tidbits. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.