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.
Answer Posted / 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 |
Post New Answer View All Answers
Search for: what is pair in c++?
What is doubly linked list in c++?
What is the purpose of templates in c++?
You have two pairs: new() and delete() and another pair : alloc() and free(). Explain differences between eg. New() and malloc()
Can we make any program in c++ without using any header file and what is the shortest program in c++.
What methods can be overridden in java?
What is size of string in c++?
What are the three forms of cin.get() and what are their differences?
What is the difference between the functions rand(), random(), srand() and randomize()?
What are function prototypes?
What are the two main components of c++?
What do you mean by public protected and private in c++?
What is a driver program?
Explain what are mutator methods in c++?
Is it possible for the objects to read and write themselves?