Algorithm for Maximum Subsequence Sum

[shahab.burki]

Hi,

I am trying to develop an efficient algorithm for maximum subsequence sum. But I am stuck.

I want to return the start and the end of the subsequence producing the maximum sum.

Example Array Contains...

-2,11,-4,13,-5,-2

Now my algorithm works as follow.

MSS(Array[],N)//Where N is the number of elements in array
{

   sum=0; //current sum
   max-sum=0;//Maximum Sum
   seq-start=0;//start of the subsequence
   seq-end=0;//end of the subsequence

   for(i=0;i<N;i++){

   sum=sum+Array[i];

   if(sum<0){

    sum=0;
    seq-start++;


  }
 else{

      if(sum>max-sum)
         max-sum=sum;

      seq-end++;
}




}


}

Please help in this regard.

Thanks

[apines]

You are iterating only once on the entire array, so I can't how your algorithm will work...
I didn't check my code, but I think that should do the trick. It goes around all the subsequences possible and returns the start, end and max value of the subsequence with the highest value. Hope it helps.

MSS(Array[],N)//Where N is the number of elements in array
{
	sum=0; //current sum
	max-sum=0;//Maximum Sum
	seq-start=0;//start of the subsequence
	seq-end=0;//end of the subsequence
	for(i = 0; i < N; ++i)
	{
		for(j = i; j < N; ++j)
		{
			sum = 0;
			for(k = i; k <= j; ++k)
			{
				sum = sum + Array[k];
			}
			if(sum > max-sum)
			{
				max-sum = sum;
				seq-start = i;
				seq-end = j;
			}
		}
	}
}

Edit: I have found another thread on this site: http://www.daniweb.com/forums/thread49177.html discussing the same problem. Rashakil Fol had a nice idea there - a direct link to the post is http://www.daniweb.com/forums/post230344.html#post230344
His idea is better than mine.

[shahab.burki]

Yes..It is the trick..You have to optimize the algorithm.. I require onley one loop. Becaue if you put three instead of one, the time complexity of the algorithm will become O^3. I want it to be O(n).

[Momerath]

This is psuedo code for max subsequence sum, you'll have to add your own start/end info:

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    /* invariant: maxendinghere and maxsofar 
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

This is from John Bentley's Programming Pearls and runs in linear time (O(n)).

[apines]

Yes..It is the trick..You have to optimize the algorithm.. I require onley one loop. Becaue if you put three instead of one, the time complexity of the algorithm will become O^3. I want it to be O(n).

Ok, then your first approach seems correct. This should do the trick in linear time:

// pseudo code, c syntax just for the more convenient highlighting :)
MSS(arr[], N)
{
   maxSum = currSum = seqStart = seqEnd = 0;
   for(i = 0; i < N; ++ i)
   {
      currSum += arr[i];
      if(currSum > maxSum)
      {
	maxSum = currSum;
	seqStart = start;
	seqEnd = i;
      }
      else if(currSum < 0) 
      {
	start = i + 1;
	currSum = 0;
      }
   }
   return maxSum, seqStart, seqEnd;
}