Program to find the largest sum of contiguous integers in the array. O(n)

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..

-Wadoo

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?

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