473,836 Members | 1,479 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Algorithm

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 14612
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<i2<=N.
Note: You may have to use another type for subsum if the sum
becomes too large.

I do not know what "KBL" is supposed to mean.
If you do not either, start with the following:
- write a function to maximise subsum for a given index pair by
only removing entries from the start and end of the subarray
that diminish the sum, that is: increase/decrease the indices
- think how you can increase the subsum by other analyses.
- how can "splitting" a subarray help.

For more algorithm questions, ask in comp.programmin g; for problems
when writing your programme, come here.
Be sure to read
http://clc-wiki.net/wiki/Introduction_to_comp.lang.c
first.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Apr 22 '06 #2
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
On 2006-04-22 10:43:13 +0200, "Nick Keighley"
<ni************ ******@hotmail. 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?


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 <se******@mac.c om>

The optimist thinks this is the best of all possible worlds.
The pessimist fears it is true. [J. Robert Oppenheimer]

Apr 22 '06 #4
[Followups set to comp.programmin g]

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

Sensei wrote:
On 2006-04-22 10:43:13 +0200, "Nick Keighley"
<ni************ ******@hotmail. 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?
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
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 "Programmin g 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
"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?


Strictly speaking this is OT for c.l.c, but it came up in another
newsgroup a while ago, and I published this solution. I believe it
to be accurate, but have not proven so. Have at it. :-)

/* How to find the maximum sum of at least L consecutive
integers given a sequence of N integers. */

/* Public Domain by CB Falconer, 2006-03-06 */

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAXRUN 100
typedef int (*instream)(voi d); /* how to get values */

/* -------------- */

void help(void)
{
fprintf(stderr, "Usage: maxsum <n> <l> [any]\n"
"where n < %d and l < n\n"
"Finds maximum sum of at least l consecutive\n"
"integers in a sequence of n integers\n"
"\n[any] entry enables debug display\n",
MAXRUN);
exit(EXIT_FAILU RE);
} /* help */

/* -------------- */

int getint(char *s)
{
long test;
char *endptr;

test = strtol(s, &endptr, 10);
if ((test > MAXRUN) || (test <= 0)) help(); /* and exit */
return test;
} /* getint */

/* -------------- */

int column;

/* setting column < 0 inhibits all display */
void showitem(int item, int itemcnt)
{
if (column >= 0) {
if (!itemcnt) column += printf("%10d ", item);
else column += printf("%10d,%-2d", item, itemcnt);
if (column > 64) {
column = 0; putchar('\n');
}
}
} /* showitem */

/* -------------- */

size_t maxcount;
#define initnext(count) maxcount = count

/* get the next integer from the input stream */
int next(void)
{
int value;

if (!maxcount) return EOF;
else maxcount--;
do {
value = (rand() % 65) - 32; /* symettric about 0 */
} while (EOF == value);
return value;
} /* next */

/* -------------- */

/* A list of these items holds the pertinent input history */
struct sofar {
int sumtohere;
struct sofar *next;
};

/* -------------- */

struct sofar *discard(struct sofar *trail)
{
struct sofar *t;

t = trail->next;
free(trail);
return t;
} /* discard */

/* -------------- */

struct sofar *newitem(int value)
{
struct sofar *item;

if (!(item = malloc(sizeof *item))) {
fprintf(stderr, "Out of memory, halting\n");
exit(EXIT_FAILU RE);
}
item->sumtohere = value;
item->next = NULL;
return item;
} /* newitem */

/* -------------- */

/* solve the real problem */
int solve(instream getnext, int l)
{
int v, items;
int sum, maxsum;
struct sofar *trail, *current, *temp;

/* initialize detection */
current = trail = newitem(0);
sum = maxsum = items = 0;

while (EOF != (v = getnext())) {
/* process v into the system */
items++;

temp = newitem(v + current->sumtohere);
current->next = temp;
current = temp;

while (trail->next->sumtohere <= trail->sumtohere
&& items > l) {
/* oldest input value is negative or zero so */
/* the sum can only be imcreased by discard */
trail = discard(trail);
items--;
}

sum = current->sumtohere - trail->sumtohere;
while ((sum <= 0) && (items > l)) {
/* The only purpose of the older entries is */
/* to enable inclusion of a future series */
/* without demanding the item count start */
/* from this current point. This may drive */
/* the sum more negative. The preceding */
/* while loop will eventually handle that */
trail = discard(trail);
items--;
sum = current->sumtohere - trail->sumtohere;
}

showitem(v, 0);
if ((sum >= maxsum) && (items >= l)) {
maxsum = sum;
showitem(sum, items);
}
}
return maxsum;
} /* solve */

/* -------------- */

int main(int argc, char **argv)
{
int n, l;
int ans;

if (argc < 3) help();
else {
if (3 == argc) column = -1; /* inhibit debug */
n = getint(argv[1]);
l = getint(argv[2]);
if (l > n) help();
initnext(n);

ans = solve(next, l);

if (column > 0) putchar('\n');
printf("Max. sum is %d\n", ans);
}
return 0;
} /* main */

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Also see <http://www.safalra.com/special/googlegroupsrep ly/>

Apr 22 '06 #8

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
8892
by: Jack Smith | last post by:
Hello, any help appreciated with following problem. I figured out the algorithm (I think), just having trouble proving it is optimal. Suppose we are given n tasks each of which takes 1 unit time to complete. Suppose further that each task has a deadline by which it is expected to finish. IF a task is not finished by the deadline, a standard penalty of $10 is applied. The problem is to find a schedule of the tasks that minimizes the...
16
2667
by: cody | last post by:
I have to write an algorithm with must ensure that objects are put in buckets (which are always 4 in size). The objects have two properties: A and B. It is not allowed that in a bucket are objects with the same A or B value. But there can be more than one object with A = null or B = null in the bucket. Sometimes there is only one valid solution, sometimes there are more valid solutions, and sometimes there isn't a complete solution at...
10
4988
by: bpontius | last post by:
The GES Algorithm A Surprisingly Simple Algorithm for Parallel Pattern Matching "Partially because the best algorithms presented in the literature are difficult to understand and to implement, knowledge of fast and practical algorithms is not commonplace." Hume and Sunday, "Fast String Searching", Software - Practice and Experience, Vol. 21 # 11, pp 1221-48
32
76464
by: Cmorriskuerten | last post by:
HI, is this is this solution to test if a number is a prime number or not: /* * Is n a prime number? * Return TRUE (1): n is a prime number * Return FALSE (0): n is a *not* a prime number */ int is_prime_number(int n)
2
2108
by: ben | last post by:
hello, i'm following an algorithm book and am stuck on an early excersise in it, not because of the c programming side of it or even the algorithm side of it, i don't think, but because of maths. i don't really understand what is expected, or really what the question means. could anyone explain what the question's after please? any help much appreciated. thanks, ben. Prove an upper bound on the number of machine instructions required to
113
12363
by: Bonj | last post by:
I was in need of an encryption algorithm to the following requirements: 1) Must be capable of encrypting strings to a byte array, and decyrpting back again to the same string 2) Must have the same algorithm work with strings that may or may not be unicode 3) Number of bytes back must either be <= number of _TCHARs in * sizeof(_TCHAR), or the relation between output size and input size can be calculated simply. Has to take into account the...
4
4289
by: FBM | last post by:
Hi, I am working on a program that simulates one of the elements of ATM. The simulation stores events which occurs every some milliseconds for a certain amount of time. Every time that an event is stored in a double linked list, the whole list is sorted for the next round. My problem appears when subjecting the program to heavy load, that is, when I run the simulation for more than 10,000 miliseconds (every event occurs in...
2
7299
by: Julio C. Hernandez Castro | last post by:
Dear all, We have just developped a new block cipher called Raiden, following a Feistel Network structure by means of genetic programming. Our intention now consists on getting as much feedback as possible from users, so we encourage you to test the algorithm and send us your opinion. We would also like to receive enhancements and new versions of the algorithm, developed in other source languages and platforms. Our idea on developing...
0
2973
by: aruna | last post by:
hey guys i earlier had very valuable responses from you all for base64 encoding algorithm.so thank for that. so now i need your assistance to do a float encoding algorithm. you may wonder why i'm so interest about this encoding algorithms. because our group is going to do a project under the ITU-T Recommendation X.891. this is named as fast infoset. this is an open source project in c language. there is an implementation in java which by...
1
3117
by: almurph | last post by:
Hi everyone, Concerning the Needleman-Wunsch algorithm (cf. http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm) I have noticed a possible loop. Inside the algorithm there is an important decision making mechanism. Its a "if, else if, else if" structure like:
0
9813
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9665
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
10834
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10541
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10584
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
1
7782
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
6976
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
5817
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4446
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.