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.

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

Is This Answer Correct ?    3 Yes 31 No

Post New Answer

More C++ General Interview Questions

Why do we need c++?

0 Answers  


What is extern c++?

0 Answers  


What is the difference between struct and class?

1 Answers  


What is meant by the term name mangling in c++?

0 Answers  


What are the advantage of using register variables?

0 Answers  






Should I learn c or c++ or c#?

0 Answers  


What you know about structures in C++?

0 Answers   Agilent, ZS Associates,


Difference between a homogeneous and a heterogeneous container

0 Answers  


What is c++ map?

0 Answers  


How many types of classes are there in c++?

0 Answers  


Find out the bug in this code,because of that this code will not compile....... #include <iostream> #include <new> #include <cstring> using namespace std; class balance { double cur_bal; char name[80]; public: balance(double n, char *s) { cur_bal = n; strcpy(name, s); } ~balance() { cout << "Destructing "; cout << name << "\n"; } void set(double n, char *s) { cur_bal = n; strcpy(name, s); } void get_bal(double &n, char *s) { n = cur_bal; strcpy(s, name); } }; int main() { balance *p; char s[80]; double n; int i; try { p = new balance [3]; // allocate entire array } catch (bad_alloc xa) { cout << "Allocation Failure\n"; return 1; }

2 Answers   Impetus,


Explain the difference between class and struct in c++?

0 Answers  


Categories