You're given an array containing both positive and negative integers and

You're given an array containing both positive and negative
integers and required to find the sub-array with the largest
sum (O(N) a la KBL). Write a routine in C for the above.

Question Posted / sujan

4 Answers
12373 Views
I also Faced
E-Mail Answers

Answers were Sorted based on User's Feedback

You're given an array containing both positive and negative integers and required to find the..

Answer / gopika

how to get O(N) for above program

Is This Answer Correct ?

1 Yes

0 No

You're given an array containing both positive and negative integers and required to find the..

Answer / gopika

main()
{
int arr[100],sz,i,max,j,k,sum;
int start,end;
printf("\nEnter size :");
scanf("%d",&sz);
printf("\nEnter elements : ");
for(i=0;i<sz;i++)
scanf("%d",&arr[i]);

max=arr[0];

for(j=1;j<=sz;j++)
for(i=0;i<sz-j+1;i++)
{ sum=0;
for(k=0;k<j;k++)
{
sum+=arr[i+k];
if(sum>max)
{
max=sum;
start=i;
end=i+k;
}

}
}

printf("\nMax is %d\nStart %d\nend %d",max,start,end);
getch();
}

Is This Answer Correct ?

0 Yes

1 No

You're given an array containing both positive and negative integers and required to find the..

Answer / monti

#include<iostream>

using namespace std;

int maxsum(int arr[], int size, int& strt_index, int&
end_index){
int max=0;
for(int i =0;i<size;i++){
max += arr[i];
strt_index = 0;
end_index = size-1;
}

int strt = 0;
int sum;

for(int i=0;i<size;i++){
sum =0;
for(int j = i; j<size; j++){
sum += arr[j];
if(sum >=max){
max = sum;
strt_index = strt;
end_index = j;
}
}
strt++;
}
return max;
}

int main(){
int strt, end;
int arr[10] = {0, 4, -5, 13, 8, -11, -2, 7, 9, -11};

int maxsub = maxsum(arr, 10, strt, end);

cout<<"\nMAX Sub Sum is : "<<maxsub;
cout<<"\nstarting index : "<<strt;
cout<<"\nEnding index : "<<end<<endl<<endl;

system("Pause");
return 0;
}

Is This Answer Correct ?

0 Yes

5 No

You're given an array containing both positive and negative integers and required to find the..

Answer / sujan

#include<iostream>
#define SIZE 16
using namespace std;
int main()
{
int a[SIZE] = {-3, 5, -9, 4, -6, -24, -13, -14, -3, -20,
-45, -11, -2, -8, 1,10};
int temp[SIZE];
int j=0,sum=0;
for(int i=0;i<=SIZE;i++)
{
if(a[i]>0)
{
temp[j]=a[i];

j++;
}

}
cout<<"Sub-array:";
for(int k=0;k<j-1;k++)
{
sum+=temp[k];
cout<<temp[k]<<"\t";
}

cout<<"\n"<<"Sum:"<<sum<<endl;

system("pause");
}