432,117 Members | 1,093 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,117 IT Pros & Developers. It's quick & easy.

# Algorithm

 P: n/a You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) a la KBL). Write a routine in C for the above Any pointers on the above problem will help. Wont sum of all positive numbers will be the largest sub-array? Apr 22 '06 #1
7 Replies

 P: n/a 11******@gmail.com schrieb: You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) a la KBL). Write a routine in C for the above Any pointers on the above problem will help. Wont sum of all positive numbers will be the largest sub-array? This sounds more like a problem with terms. Let us rephrase it: Given A, an array N of signed long, find one index pair (i1, i2) such that signed long subsum = 0; size_t i; for (i = i1; i < i2; i++) sum += A[i]; yields the maximal subsum possible for 0<=i1

 P: n/a 11******@gmail.com wrote: You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) a la KBL). Write a routine in C for the above Any pointers on the above problem will help. Wont sum of all positive numbers will be the largest sub-array? I assume a "sub-array" has to be contiguous. 3 3 -1 3 The sub-array with the largest sum is the entire array -- Nick Keighley Apr 22 '06 #3

 P: n/a On 2006-04-22 10:43:13 +0200, "Nick Keighley" said: You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) a la KBL). Write a routine in C for the above Any pointers on the above problem will help. Wont sum of all positive numbers will be the largest sub-array? I assume a "sub-array" has to be contiguous. 3 3 -1 3 The sub-array with the largest sum is the entire array Not always (e.g. +3 +3 +3 +3 +3 -3 -3 -3 -3 -3), and this is OT, nothing related to C. -- Sensei The optimist thinks this is the best of all possible worlds. The pessimist fears it is true. [J. Robert Oppenheimer] Apr 22 '06 #4

 P: n/a [Followups set to comp.programming] 11******@gmail.com said: You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) a la KBL). Write a routine in C for the above Any pointers on the above problem will help. Wont sum of all positive numbers will be the largest sub-array? No, because they might not be contiguous. Consider 1, -3, 2. The sub-arrays are: 1, -3, 2 : sum is 0 1, -3 : sum is -2 1 : sum is 1 -3, 2 : sum is -1 -3 : sum is -3 2 : sum is 2 So in this case, the largest sub-array does not include one of the positive numbers. Here's a possible approach to your problem which would be an O(N) solution - comments welcomed. You know that your array will consist of zero or more groups of one or more positive (or rather, non-negative) numbers, and zero or more groups of one or more negative numbers. Firstly, we can ignore leftmost and rightmost negative values (unless the entire array is filled with negative values, in which case the solution is the single least negative value. For simplicity, that solution can easily be determined in a single separate pass. (Remember that we can have as many passes as we like and still retain O(N) behaviour, provided that the number of passes does not depend on any variable, such as N). sum = INT_MIN; /* or LONG_MIN, or whatever you're using */ nonneg = 0; for(i = 0; !nonneg && i < lim; i++) { if(arr[i] >= 0) { nonneg = 1; } else if(nonneg > sum) { sum = nonneg; left = i; right = i; } } If the array is filled with non-negative values, the solution is the whole array. Again, this can be determined in a single pass: sum = 0; neg = 0; for(i = 0; !neg && i < lim; i++) { if(arr[i] < 0) { neg = 1; } else { sum += arr[i]; /* beware overflow, obviously */ } } if(!neg) { left = 0; right = lim - 1; } So setting those aside as solved problems, we tackle the case where we have at least one non-negative value. (I may slip, and say "positive" when I mean "non-negative" - clearly, a 0 value can be added to any sub-array without diminishing its value, so for the rest of this thread I will allow myself to be a little sloppy with the term "positive".) As I said above, we can ignore all the negative values on the left and right of the array, so let's pretend they're not there. We now have a setup like this: A - B + C - D + E - F + (...) where A, B, etc represent the magnitudes of contiguous positive and negative number groups, alternately. At the beginning of the loop, these values are not known. We start off by summing A (and carefully recording its limiting indices). Our tentative solution is [A] (by which I mean the subarray consisting entirely of the A subarray). We then sum B, again carefully recording its limits. If B > A, then A - B will be negative, so there is no advantage to retaining A (unless it is the only positive group, in which case it is, of course, the solution); A and B between them effectively form a leftmost negative group, so they can be discarded, and we simply go round again. If A >= B, though, then the whole subarray that includes A and B contributes to (or at least does not detract from) a solution. So we can now accumulate A, B, and C into a single subarray which we know will have a positive value. That is, our tentative solution is now [A - B + C] - D + E - F + (...) Because [A - B + C] is effectively a single subarray, we are now in the same position as before, i.e. alternating positive and negative subarrays, so we simply go round again until we run out of data. This method starts off by identifying and evaluating two subarrays, and then identifies and evaluates each subsequent subarray in turn, either accreting it or rejecting all the results so far, so it can be done in one linear pass. Writing the C code is left as a fairly trivial exercise. (The only mildly tricky bit is making sure you don't overflow.) -- Richard Heathfield "Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk email: rjh at above domain (but drop the www, obviously) Apr 22 '06 #5

 P: n/a Sensei wrote: On 2006-04-22 10:43:13 +0200, "Nick Keighley" said: You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) a la KBL). Write a routine in C for the above Any pointers on the above problem will help. Wont sum of all positive numbers will be the largest sub-array? I assume a "sub-array" has to be contiguous. 3 3 -1 3 The sub-array with the largest sum is the entire array Not always (e.g. +3 +3 +3 +3 +3 -3 -3 -3 -3 -3), I meant "in this particular case". I was giving a counter example to the OPs claim. and this is OT, nothing related to C. yup -- Nick Keighley Apr 22 '06 #6

 P: n/a 11******@gmail.com wrote: You're given an array containing both positive and negative integers and required to find the sub-array with the largest sum (O(N) a la KBL). Write a routine in C for the above Any pointers on the above problem will help. Wont sum of all positive numbers will be the largest sub-array? This problem is straight out of "Programming Pearls" or "More Programming Pearls". Any serious programmer should own these. -- Julian V. Noble Professor Emeritus of Physics University of Virginia Apr 22 '06 #7 