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

Answers were Sorted based on User's Feedback



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

Answer / senthilkumar

#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int lsum,sum,i,j,n,a[20],flag=0;
lsum=0;sum=0;
cout<<"Enter the total no. of elements:";
cin>>n;

for(i=0;i<n;i++)
cin>>a[i];

//Checking condition whether there are only negative numbers
for(i=0;i<n;i++)
{
if(a[i]>0)
flag++;
}
//for array including positive and negative numbers
if(flag>0)
{
for(i=0;i<n;i++)
{
sum+=a[i];
if(sum<0)
{
sum=0;
j++;
i=j;
}
else if(lsum<sum)
lsum=sum;
}
}
//for array having only negative numbers
else
{
lsum=a[0];
for(i=0;i<n;i++)
{
if(lsum<a[i])
lsum=a[i];
}
}
cout<<"The largest sum is:"<<lsum;
getch();
}

Is This Answer Correct ?    6 Yes 1 No

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

Answer / raghuram.a

#include <iostream.h>
#include<conio.h>
/*prints subarray producing maximum sum..Efficiency is O(n)*/
main()
{
int flag=0,n,i,c=0,sum=0,max=0,a[25],s=-1,e=-1;
cout<<"enter n:";
cin>>n;
cout<<"enter elements:";
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
{
if(a[i]+sum>0)
sum+=a[i];
else
{
sum=0;
if(c!=0)
c=1;
}
if(sum>max)
{
max=sum;
e=i;
s=e-c;
c++;
}
}
cout<<"max sum is:"<<max;
cout<<"\n\nmax sum producing sub array is:";
if(s!=-1&&e!=-1)
for(i=s;i<=e;i++)
cout<<"\t"<<a[i];
getch();
return 0;
}

Is This Answer Correct ?    11 Yes 9 No

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

Answer / saurabh

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

int main()
{
int arr[50];
int i,sum1,sum2,n;
int flag;
//int front1,front2,rear1,rear2;
printf("How many elements do you want to enter: ");
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&arr[i]);
sum1=arr[0];
sum2=arr[0];
if(arr[0]<0)
flag=1;
else
flag=0;
for(i=1;i<n;i++)
{
if(flag==1)
{

if((arr[i]>0&&arr[i-1]<0)||(arr[i]<0&&arr[i-1]<0&&arr[i]>arr[i-1]))
sum2=0;
if(arr[i]<0&&arr[i-1]<0&&arr[i]<arr[i-1])
{
int temp=arr[i];
arr[i]=arr[i-1];
arr[i-1]=arr[i];
sum2=0;
}
if(arr[i]<0&&arr[i-1]>0&&(arr[i-1]+arr[i])<0)
sum1=arr[i-1];
}
sum2=sum2+arr[i];
if(sum2>sum1)
{
sum1=sum2;
flag=0;
}
if(sum2<0)
{
sum2=0;
sum2=sum2+arr[i];
flag=1;
}
}
//printf("%d",rear);
if(sum1>=sum2)
printf("Largest subarray sum= %d\n",sum1);
else
printf("Largest subarray sum= %d\n",sum2);
return 0;
}

Is This Answer Correct ?    2 Yes 0 No

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

Answer / jjaspirin

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

}

Is This Answer Correct ?    3 Yes 2 No

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

Answer / somebody

Guys..Answer 3 is correct..When there are -ve
numbers..maximum sum is 0.U should not consider any elements
at all..Coz null set which has maximum sum.i.e 0.So the 4th
ans is right.

Is This Answer Correct ?    2 Yes 2 No

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

Answer / raghuram.a

#include <iostream.h>
#include<conio.h>
main()
{
int s=-1,m=1,n,max=0,e=-1,sum=0,i,a[20];
cout<<"enter n:";
cin>>n;
cout<<"enter elements:";
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n;i++)
{
if(m==1)
{
if(a[i]>0)
s=i;
m=0;
}
if(a[i]+sum>0)
sum+=a[i];
else
{

m=1;
sum=0;
}
if(sum>max)
{
max=sum;
e=i;
}
}
cout<<"max sum is:"<<max;
cout<<"\n\nmax sum producing sub array is:";
if(s!=-1&&e!=-1)
for(i=s;i<=e;i++)
cout<<a[i]<<"\t";
getch();
return 0;
}

Is This Answer Correct ?    11 Yes 13 No

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

Answer / dilip

i think ths program doesnt not work when the sum is
negative.. cant we not work around it by setting the max as
somelarge negative value and comparing with that??

Is This Answer Correct ?    3 Yes 5 No

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

Answer / deepika jadav

the cod is written in c#...similar to java and c.....so interpret it accordingly..

static void Main(string[] args)
{
//int[] arr={2,3,-5,-2,-2,5,6,7,8,-2,3,4};
int[] arr = {-2,-3,-4,-5,-6,-7 };
int max=0;
int sum=0;

int min = 0;
int flag = 0;
for (int i = 0; i < arr.Length;i++)
{
if (arr[i] < 0)
{
sum = 0;
flag++;
if(flag==1)
min = arr[i];
if (flag == arr.Length)
Console.WriteLine("The smallest no amogst negative nos is {0} hence the largest aum is {1}",min,min);
if (min < arr[i])
min = arr[i];
continue;
}
else
{
sum = sum + arr[i];
}

if (max < sum)
max = sum;


}
if(flag!=arr.Length)
Console.WriteLine("the Largest Sum is {0}",max);
Console.ReadLine();
}

Is This Answer Correct ?    0 Yes 2 No

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

Answer / raghuram.a

Actually I have posted 3 answers..Bcoz after posting twice I
found there are some logical errors.Last one is fully
correct..If not please let me know..

Is This Answer Correct ?    2 Yes 7 No

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

Answer / raghuram.a

/*prints subarray producing maximum sum.Efficiency is O(n)*/
#include <iostream.h>
#include<conio.h>
main()
{
int n,i,c=0,sum=0,max=0,a[25],s=-1,e=-1;
cout<<"enter n:";
cin>>n;
cout<<"enter elements:";
for(i=1;i<=n;i++)
cin>>a[i];
for(i=1;i<=n;i++)
{
if(a[i]+sum>0)
{
sum+=a[i];
if(sum>=max)
s=i-c;
c++;
}
else
{
sum=0;
c=0;
}
if(sum>max)
{
max=sum;
e=i;
}
}
cout<<"max sum is:"<<max;
cout<<"\n\nmax sum producing sub array is:";
if(s!=-1&&e!=-1)
for(i=s;i<=e;i++)
cout<<"\t"<<a[i];
getch();
return 0;
}

Is This Answer Correct ?    4 Yes 10 No

Post New Answer

More C Code Interview Questions

main() { int x=5; clrscr(); for(;x<= 0;x--) { printf("x=%d ", x--); } } a. 5, 3, 1 b. 5, 2, 1, c. 5, 3, 1, -1, 3 d. –3, -1, 1, 3, 5

2 Answers   HCL,


write a program to count the number the same (letter/character foreg: 's') in a given sentence.

2 Answers  


main() { char c=' ',x,convert(z); getc(c); if((c>='a') && (c<='z')) x=convert(c); printf("%c",x); } convert(z) { return z-32; }

1 Answers  


Is the following code legal? struct a { int x; struct a b; }

1 Answers  


void main() { int c; c=printf("Hello world"); printf("\n%d",c); }

2 Answers  


program to Reverse a linked list

12 Answers   Aricent, Microsoft, Ness Technologies,


What is the subtle error in the following code segment? void fun(int n, int arr[]) { int *p=0; int i=0; while(i++<n) p = &arr[i]; *p = 0; }

1 Answers  


main() { extern int i; i=20; printf("%d",sizeof(i)); }

2 Answers  


Which one is taking more time and why ? :/home/amaresh/Testing# cat time.c //#include <stdio.h> #define EOF -1 int main() { register int c; while ((c = getchar()) != EOF) { putchar(c); } return 0; } ------------------- WIth stdio.h:- :/home/amaresh/Testing# time ./time_header hi hi hru? hru? real 0 m4.202s user 0 m0.000s sys 0 m0.004s ------------------ Witout stdio.h and with #define EOF -1 =================== /home/amaresh/Testing# time ./time_EOF hi hi hru? hru? real 0 m4.805s user 0 m0.004s sys 0 m0.004s -- From above two case , why 2nd case is taking more time ?

0 Answers  


main() { int a=10,*j; void *k; j=k=&a; j++; k++; printf("\n %u %u ",j,k); }

1 Answers  


In a gymnastic competition, scoring is based on the average of all scores given by the judges excluding the maximum and minimum scores. Let the user input the number of judges, after that, input the scores from the judges. Output the average score. Note: In case, more than two judges give the same score and it happens that score is the maximum or minimum then just eliminate two scores. For example, if the number of judges is 5 and all of them give 10 points each. Then the maximum and minimum score is 10. So the computation would be 10+10+10, this time. The output should be 10 because 30/3 is 10.

0 Answers   TCS,


How can u say that a given point is in a triangle? 1. with the co-ordinates of the 3 vertices specified. 2. with only the co-ordinates of the top vertex given.

1 Answers  


Categories