Max Subsequence Problem (Optimizing Algorithm/Program Step by Step)

Problem:
Given a sequence of integers A1, A2, …, An, find the maximum possible value of a subsequence Ai, …, Aj.
Numbers can be negative.
You want a contiguous chunk with largest sum.

Example:   -2, 11, -4, 13, -5, -2
The answer is  20    (subseq.  A2 through A4).

    Algo I :

        int Sum = 0;

 for( int i = 0; i < a.size( ); i++ )
 for( int j = i; j < a.size( ); j++ )
 {
 int thisSum = 0;
 for( int k = i; k <= j; k++ )
 thisSum += a[ k ];
 if( thisSum > maxSum ) maxSum   = thisSum;
 }
 return maxSum;

    Complexity: O(n3)               [algo not good for large number of inputs e.g, size > 10 ^7]

    Algo II :

    into maxSum = 0;

 for( int i = 0; i < a.size( ); i++ )
 int thisSum = 0;
 for( int j = i; j < a.size( ); j++ )
 {
      thisSum += a[ j ];
      if( thisSum > maxSum )
   maxSum   = thisSum;
 }
 return maxSum;

    Complexity: O(n2)               [just good... ]
 
     
    Algo III:

        This algorithm uses divide-and-conquer paradigm. The max subsequence is entirely in the left half, entirely in the right half, or it straddles the midpoint.
Example:
 left half  | right half
 4   -3   5 -2 |    -1  2  6   -2
 Max in left is  6  (A1 through A3); max in right is  8  (A6 through A7). But straddling max is 11 (A1 thru A7).  


    How do we find the straddling max subsequence?
    Key Observation:
        Left half of the straddling sequence is the max subsequence ending with -2.
        Right half is the max subsequence beginning with -1.

        A linear scan lets us compute these in O(n) time.

        The divide and conquer is best analyzed through recurrence:

 T(1) = 1
 T(n) = 2T(n/2) + O(n)

        This recurrence solves to T(n) = O(n log n).
   
    Complexity: O(nlog(n))               [better ...still not best ]


    Algo IV:


 int maxSum = 0, thisSum = 0;

  for( int j = 0; j < a.size( ); j++ )
 {
 thisSum += a[ j ];

 if ( thisSum > maxSum )
 maxSum = thisSum;
 else if ( thisSum < 0 )
 thisSum = 0;
 }
     return maxSum;
        }

     Complexity: O(n)               [ best ]