Given a sequence of integers, find a continuous subsequence which
maximizes the sum of its elements, that is, the elements of no other
single subsequence add up to a value larger than this one. An empty
subsequence is considered to have the sum 0; thus if all elements are
negative, the result must be the empty sequence.
Solution:O(n^2) i want O(nlogn).......???????????????????
#include <stdio.h>
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
int main()
{
int a[] = {-1 , -2 , 3 , 5 , 6 , -2 , -1 , 4 , -4 , 2 , -1};
int length = 11;
int begin, end, beginmax, endmax, maxsum, sum, i;
sum = 0;
beginmax = 0;
endmax = -1;
maxsum = 0;
for (begin=0; begin<length; begin++) {
sum = 0;
for(end=begin; end<length; end++) {
sum += a[end];
if(sum > maxsum) {
maxsum = sum;
beginmax = begin;
endmax = end;
}
}
cout<<sum<<"\t";
}
cout<<endl;
for(i=beginmax; i<=endmax; i++) {
printf("%d\n", a[i]);
}
getch();
}
its has time complexity O(n^2) ..does better solution exist
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
