Welcome, %1$s. Please login or register.

September 26, 2017, 06:28:25 PM
: 1
: Find the largest sum!  ( 2405 )
« : June 18, 2007, 09:20:52 PM From Poonam»



Find the largest sum!


Given an array of integers, write an algorithm or a program to find the largest consecutive sum in the array. The array can have both negative and positive elements.

 
Liked It? Share it!

              


« #1 : June 20, 2007, 04:16:04 PM From Abhay»

main()
{
int i,j, n,a[100],sum=0,temp=0;
printf("\n enter a array size");
scanf("%d",&n);
printf("\n enter %d elements",n);
for(i=0;i<n;i++)
scanf("%d",&a);
for(i=0;i<n;i++)
{temp=0;
for(j=i;j<n;j++)
{ temp+=a[j];
if(temp>sum)
sum=temp;
}
}
printf("\n largest contiguous sum is: %d",sum);
}
« #2 : June 23, 2007, 11:41:44 AM From Prateek»

Abhay, your solution isn't perfect. What if all the numbers in the array are negative? Your solution will give an answer '0' which is incorrect.
« #3 : June 26, 2007, 07:59:31 PM From Poonam»

int GetTheLargestConsecutiveSum(int a[], int n)
{
   int current_sum=0, highest_sum;

   highest_sum = a[0];
   for(i=0;i<n;i++)
   {
      current_sum += a[ i ];
      if( highest_sum < current_sum )
         highest_sum = current_sum;
      if( current_sum < 0 )
         current_sum = 0;
   }
   printf("\nLargest contiguous sum is: %d", highest_sum);
}
« #4 : November 22, 2007, 06:11:58 PM From iammilind»

Hi Guru,
The only small edit is, I have found the indices also.
========================================

#include<stdio.h>

void Find_the_Largest_Sum(const int a[], const int SIZE)
{
    int LowerIdx=0,LowerTmp=0;
    int HigherIdx=0,HigherTmp=0;
    int Maximum=0,Total=0;
    int i;

    for(i=0; i<SIZE; i++)
    {
        Total += a[ i ];
        if(Total < 0)
        {
            Total = 0;
            LowerTmp = i + 1;
        }
        else if(Total <= Maximum)
             HigherTmp = i;
        else
        {
             LowerIdx  = LowerTmp;
             HigherIdx  = HigherTmp = i;
             Maximum  = Total;
        }
     }

     printf("Lower  Index  = %d\nHigher Index  = %d\nMaximum \
             Total = %d\n",LowerIdx,HigherIdx,Maximum);
}

void main()
{
    int a[]={-130,120,170,-300,-10,150,150,-20,30,-300,222};
    Find_the_Largest_Sum(a, sizeof(a)/sizeof(*a));
}
: 1
« previous next »

 

Best RatedList All>>



Latest
Random



SMF 2.0.10 | SMF © 2015, Simple Machines | Contact Webmaster | OnlineFunDb.com © 2009/10 | Legal Disclaimer