# Given a integer array, find the subsequence with max sum.

Linear Solution
There is a linear solution. The idea is to scan the sequence from start to finish keeping track of maxsofar, the maximum sum of a contiguous subsequence seen so far, and maxendinghere, the maximum sum of a contiguous subsequence which ends at the current position. Bentley's pseudo-code reads:

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


This translates directly into Python.

def max_sum_subsequence(seq):
      maxsofar = 0
      maxendinghere = 0
      for s in seq:
# invariant: maxendinghere and maxsofar are accurate
# are accurate up to s
          maxendinghere = max(maxendinghere + s, 0)
          maxsofar = max(maxsofar, maxendinghere)
      return maxsofar

Now, this is a fabulous solution. Bentley describes it as subtle. Such a succinct code snippet hardly looksdoes take a bit of understanding: subtle, but I agree, the loop body

maxendinghere = max(maxendinghere + s, 0)
maxsofar = max(maxsofar, maxendinghere)

Why does this work?

Well, essentially maxendinghere is what's accumulating the subsequences — it keeps rolling the next element into itself. Should this accumulated sum ever become negative we know that the subsequence-which-ends-here we're currently tracking is worse than the empty subsequence-which-restarts-here; so we can reset our subsequence accumulator, and the first clause of the loop invariant still holds. Combine this with the observation that maxsofar tracks peaks in maxendinghere and we're done.

The loop-invariant comment provides a good example of how comments can help us understand an algorithm, even though the code is minimal and the variable names are well-chosen.



-------- The C code ---------------

int MaxSubArray(int *a, int size, int &from, int &to)
{
int sum = 0, maxSum = 0;
for (int i = 0; i < size; ++i) {
sum += a[i];
if (sum >maxSum) {
to = i;       //  RANGE OF MAXIMUM SUB ARRAY TILL THIS POSITION
maxSum = sum;
}
else if (sum < 0) {
from = i+1;   // RANGE OF  MAXIMUM SUB ARRAY STARTS FROM THIS POSITION.
sum = 0;
}
}
return maxSum;
}

Or:::

#include <stdlib.h>
#include <iostream>
using  namespace std;
int main()
{
//Array containing the integers
int array[]=  {-2, 1,-3, 4,-1,2,1,-5,4,2,-17,9,-2,4, 5, -4};

int total = 0;
int  start = 0;
int finish = 0;
int highest = 0;
int tempstart = 0;
for(int  i=0;i <=sizeof(array)/sizeof(int) - 1; i++)
{ 
total =  total + array[i];
total = total < 0 ? 0: total;
if(total <= 0)
tempstart = i+1;
highest = highest  < total ?  total:highest;
if(total >= highest)
{
start = tempstart;
finish = i;
}
}
cout<<"from   "<<start<<" to  "<<finish<<" Produce:-  "<<highest<<endl;
return 0;
}

----------------------------

#include<iostream>
#include <stdlib.h>
using namespace std;
int max_of(int first, int second)
{
      return first > second ? first : second;
}
int main()
{
int a[] = {1, -2, -3, 4, 5, 7, -6};
int max_so_far = 0;
int max_now_here = 0;
for(int i=0; i<6;i++)
{
max_now_here = max(0, max_now_here + a[i]);
max_so_far = max(max_so_far , max_now_here);
}
cout<< "The max sum is : "<< max_so_far;
return 0;
}

♥ ¸¸.•*¨*•♫♪♪♫•*¨*•.¸¸♥
http://wordaligned.org/articles/the-maximum-subsequence-problem
http://www.careercup.com/question?id=291744