Main really should have a type: int main ( void )

This program is completely wrong. It doesn't even work for the provided test case of (-1, 2, -3, 2, 0, 5, -11).

Yes, the solution provided above is incorrect. I came to this website looking for the solution and finally ended up writing it myself. Hope this is useful for someone else.

Here is a working solution. Set the array "a" and N_ELEMENTS accordingly. Some cases are not covered but should be an easy fix.

#include <stdio.h>
#define N_ELEMENTS 7

int main() {
int a[N_ELEMENTS] = {-1, 2, -3, 2, 0, 5, -11 }; // if you change the array, make sure you change N_ELEMENTS
int i = 0;

while(a[i] < 0 && i<N_ELEMENTS) {
i++;
}

if (a[i] < 0) {

printf ("DEBUG: array with only negative numbers. Print the smallest negative number as the sum and we are done.\n");

}

int sum_p=0, sum_n = 0;
int largest_sum = 0;

while (i<N_ELEMENTS) {
if (a[i] > 0) {
sum_p += a[i];

}
else {
sum_n += a[i];

}

if (sum_p+sum_n > largest_sum) {
largest_sum = sum_p + sum_n;

}

if (sum_p+sum_n <= 0) {
// find the next positive number
while(a[i] < 0 && i<N_ELEMENTS) {
i++;
}
if (a[i] < 0 || i == N_ELEMENTS) {
break;

}

sum_p = 0;
sum_n = 0;

} else {
i++;
}
}

printf ("DEBUG: The largest consecutive sum = %d\n", largest_sum);

}

int main(void) :::
no need of it for every time, it is not necessary

what is the meaning of largest sum of contiguous integers.
i understood it as below. ( correct me if wrong )

consider the elements of the array are

-1, 2, -3, 2, 0, 5, -11

so the sums of contiguous elements will be



here the largest of all the contiguous elements sums is -4.

if this is the case how can we do it with 0(n) complexity.

consider NOE as no of elements, ele as array with NOE elemensts, sum and large are initially zero.


is there any way to do it with less complexity ?

NOTE : not compiled or tested just doc'd the idea....

void LargestContiguousSubArray(int[] a, int l, out long sum)
{
sum = -1;
if (0 == l)
{
return;
}

int i = -1;
while (i < l -1
&& 0 >= a[++i])
{
}

long tempSum = 0;

for (; i < l; i++)
{
if (tempSum + a[i] < 0)
{
sum = tempSum;
tempSum = 0;
continue;
}

tempSum += a[i];

if (sum < tempSum)
{
sum = tempSum;
}
}
}

Umm you need a dynamic programming algorithm that uses subproblems and memoization to solve this adequately. Pretty sure all of the "solutions" listed in here are wrong.

i support gaiety's answer with a slight alteration

making the sum zero as the last statement in the first for loop, so that every time it will have a new sum.

if thats not correct can someone provide a correct method.

thank you BestJew, for digging old unsolved thread.

I have found a real simple solution.

tried and tested :p

cheers..

-Wadoo