Returns the largest sum of contiguous integers in the array
Example: if the input is (-1, 2, -3, 2, 0, 5, -11), the largest sum is 7

Time complexity is O(n).

``````#include  <stdio.h>
main()
{
int i,j,n,a[20],sum=0,msum =0;

scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);

for(j=1;j<=n;j++)
{
sum+=a[j];
if(msum<sum)
msum=sum;
if(sum < 0)
sum = 0;
}
printf("\n%d",msum);
}``````

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

``````(-1) + 2 + (-3) + 2 + 0 + 5 +  (-11)   = -6
2 + (-3) + 2 + 0 + 5 +  (-11)   = -5
(-3) + 2 + 0 + 5 +  (-11)   = -7
2 + 0 + 5 +  (-11)   = -4
0 + 5 +  (-11)   = -6``````

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.

``````for ( s = 0; s <NOE-1; s++)  {
for ( x= s ; x <NOE-1 ;x++)
sum = sum+ ele[x];
if ( sum > large )
large = sum ;
}``````

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.

``````#include "stdafx.h"
#include"stdio.h"
#include"string.h"
#include"conio.h"

int main()
{
int str[20];
int size,i,j,sum,msum;
//str[0]=0;
printf("Enter array size\n");
scanf("%d",&size);
printf("Enter array elements:");
for(i=0;i<size;i++)
{
scanf("%d",&str[i]);
}
msum=0;
for(i=0;i<size;i++)
{
sum=str[i];
for(j=(i+1);j<size;j++)
{
sum=sum+str[j];
if(sum>msum)
{
msum=sum;

}
if(sum<0)
sum=0;
}

}

printf("%d",msum);
getch();
return 0;

}``````

tried and tested :p

cheers..

but that is not O(n).

it is O(n2)

never mind, i just saw the above post.

.

Iam3R:

Sorry, I didn't mean to dig up old threads. Its just that at the time, I had just studied the exact same problem and I *think* my professor made the claim that it wasn't doable without memoization (of the solutions in here, none use a dynamic programming approach afaik). It has been awhile since then, but I'm still hoping someone on here will confirm or deny that suggestion.

edit: I found some links elsewhere that say I'm wrong, http://geeksforgeeks.org/?p=576 .

I'm totally confused. Why is BestJew getting blamed for digging up an old thread? and why is BestJew apologizing? i don't see where any of this is his fault....

What about Memoization through using dictionary Class?

WaltP commented: Talk about digging up an old thread! And with 54 posts, you should know better! -3

What about Memoization through using dictionary Class?

hi everyone, i looked in this thread to find this program, but ended doing it myself. it's quite simple.below you find the code for it. are needed 2 cycles of for. one from the first element i=0 of the array till the Size-1, and the other from i+1 to Size, both of them are incremented by two, not by one. this is important. another important issue is that the sum is reset to 0 after each calculation.

#include <stdio.h>
#include <conio.h>
main()
{
int a[]={-1,-3,-5,-10,5,-2,3,-1,2,-1,10,-2};
int max_sum,sum,i,j;
sum=max_sum=a[0];
for ( i = 0; i <12; i=i+2)
for ( j=i+1;j<=12;j=j+2){
sum = a+ a[j];
if ( sum > max_sum )
max_sum = sum ;
sum=0;
}
printf("The Largest Sum Of Consecutive Numbers is %d",max_sum);
getch();
return 0;
}