crude C# O(n) soln... Haven't read the entire post... u probably
already have the answer
private string MaxSubarray(string p)
{
var array = p.Split(',');
int currentmax = -1,maxstart = -1, maxend = -1;
int firstpositveindex = -1, arraysize = array.Length;
int thissum = 0;
for(int i=0; i< arraysize; i++)
{
var thisnumber = Int32.Parse(array[i].Trim());
if (thisnumber < 0 && firstpositveindex == -1)
continue;
if(firstpositveindex ==-1)
firstpositveindex = i;
if (0 >= (thisnumber + thissum))
{
firstpositveindex = -1;
thissum = 0;
continue;
}
else
thissum = thisnumber + thissum;
if (thissum > currentmax)
{
currentmax = thissum;
maxstart = firstpositveindex;
maxend = i;
}
}
string result = string.Empty;
if (currentmax >= 0 && maxstart >= 0 && maxend >= 0)
{
for (int i = maxstart; i <= maxend; i++)
{
result = result + array[i] + ",";
}
result += "MAX=" + currentmax;
}
return result;
}
On Sep 6, 1:42 pm, bittu <[email protected]> wrote:
> 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.
