# Maximum subsequence

• 09-25-2010, 12:19 AM
dxg
Maximum subsequence
Hello, I have borrowed some code from this amazing website and am trying to modify it a bit. Any help would be much appreciated!

The follow program takes in an array "int [ ]a" and spits out the maximum subsequence. What it does NOT do is display the maximum subsequence elements {} which is what I am trying to accomplish.

I understand my description may be a bit vague so please ask any questions if necessary.

Here are a few examples:

int []a = { 4, -3, 5, -2, -1, 2, 6, -2. }
The maximum sum is 11.

What I want the program to also do is display,
The maximum sum subsequence is show below:
{ 4, -3, 5, -2, -1, 2, 6 }

Code:

```/**     * Recursive maximum contiguous subsequence sum algorithm.     * Finds maximum sum in subarray spanning a[left..right].     * Does not attempt to maintain actual best sequence.     */     private static int maxSumRec( int [ ] a, int left, int right )     {         int maxLeftBorderSum = 0, maxRightBorderSum = 0;         int leftBorderSum = 0, rightBorderSum = 0;         int center = ( left + right ) / 2;         if( left == right )  // base case             return a[ left ] > 0 ? a[ left ] : 0;         int maxLeftSum  = maxSumRec( a, left, center ); // recursive call         int maxRightSum = maxSumRec( a, center + 1, right ); // recursive call         for( int i = center; i >= left; i-- )         {             leftBorderSum += a[ i ];             if( leftBorderSum > maxLeftBorderSum )             {                 maxLeftBorderSum = leftBorderSum;                 // PUT CODE HERE ******************                } // if statement         } // for loop                 for( int i = center + 1; i <= right; i++ )         {             rightBorderSum += a[ i ];             if( rightBorderSum > maxRightBorderSum )             {                 maxRightBorderSum = rightBorderSum;                 // PUT CODE HERE ******************             } // if statement         } // for loop                 return max3( maxLeftSum, maxRightSum,                     maxLeftBorderSum + maxRightBorderSum );     } // MaxSumRec```
• 09-25-2010, 01:54 AM
Norm
What help are you looking for? Do you have any specific java programming questions?
Your question seems mostly about algorithm and logic.

What is the "// PUT CODE HERE ******************" comment for?
What code do you want there?
• 09-25-2010, 01:59 AM
dxg
I am trying to figure a way to keep track of the array position which the maximum subsequence is located.

The // PUT CODE HERE section is where I believe the appropriate information should go.
• 09-25-2010, 02:10 AM
Norm
Is the array position a single index or what?
The normal way to "keep track of" a value is to save it in a variable somewhere.
Would this technique work?
• 09-25-2010, 02:18 AM
al_Marshy_1981
your max value is 9 not 11(summing all the numbers). ur max subsequence is the addition of all highest positive values which is 17.
• 09-25-2010, 02:23 AM
dxg
Quote:

Originally Posted by Norm
Is the array position a single index or what?
The normal way to "keep track of" a value is to save it in a variable somewhere.
Would this technique work?

You are correct, however when I try the following code, I receive the result:

The max sum is 99.

And the for loop is never executed at the bottom.

Do you have any suggestions beyond that?

Thank you in advance.

Code:

```/**  * Maximum Subsequence Sum Class  */ public final class DivideAndConquer {                    [COLOR="Red"]static private int seqStart = 0;             static private int seqEnd = -1;[/COLOR]     /**     * Recursive maximum contiguous subsequence sum algorithm.     * Finds maximum sum in subarray spanning a[left..right].     * Does not attempt to maintain actual best sequence.     */     private static int maxSumRec( int [ ] a, int left, int right )     {         int maxLeftBorderSum = 0, maxRightBorderSum = 0;         int leftBorderSum = 0, rightBorderSum = 0;         int center = ( left + right ) / 2;       if( left == right )  // base case             return a[ left ] > 0 ? a[ left ] : 0;         int maxLeftSum  = maxSumRec( a, left, center ); // recursive call         int maxRightSum = maxSumRec( a, center + 1, right ); // recursive call       [COLOR="red"] for( int i = center; i >= left; i-- )         {             leftBorderSum += a[ i ];             if( leftBorderSum > maxLeftBorderSum )             {                 maxLeftBorderSum = leftBorderSum;                 // PUT CODE HERE ******************                    seqStart = center;                 seqEnd = left;             } // if statement         } // for loop[/COLOR]                 for( int i = center + 1; i <= right; i++ )         {             rightBorderSum += a[ i ];             if( rightBorderSum > maxRightBorderSum )             {                 maxRightBorderSum = rightBorderSum;                 // PUT CODE HERE ******************             } // if statement         } // for loop                 return max3( maxLeftSum, maxRightSum,                     maxLeftBorderSum + maxRightBorderSum );     } // MaxSumRec         /**     * Determine which subsequence is largest: left, right, or a     * combination of both.     */     private static int max3( int a, int b, int c )     {                return a > b ? a > c ? a : c : b > c ? b : c;     } // max3         /**     * Return 0 if array length is no great than 0, else run maxSumRec     */     public static int maxSubSum4( int [ ] a )     {         return a.length > 0 ? maxSumRec( a, 0, a.length - 1 ) : 0;     } // maxSubSum4         [COLOR="red"]/**         * Class Driver.         */         public static void main( String [ ] args )         {                 int a[ ] = { 99, -32, -55, -100 };                 int maxSum;                 maxSum = maxSubSum4( a );             System.out.println( "Max sum is " + maxSum );             for( int i = seqStart; i <= seqEnd; i++)             System.out.print(a[i] + ", ");         } // main[/COLOR]         } // DivideAndConquer```
• 09-25-2010, 02:31 AM
dxg
Quote:

Originally Posted by al_Marshy_1981
your max value is 9 not 11(summing all the numbers). ur max subsequence is the addition of all highest positive values which is 17.

The max subsequence for this program is the addition of all numbers going in order, (you may not skip over any integers). Does this make sense?

Array = { 1, 2, -5, 6, -1, 100 }

Max = 105
• 09-25-2010, 02:43 AM
al_Marshy_1981
Array = { 1, 2, -5, 6, -1, 100 } =105;
Array={100,2,-5,-1,1,6} = 105; order does not matter a jot....... summing all the elements will always give the same amount no matter what order you take when only additon and subtraction is involved. therefore like I said earlier the highest subsequence will always be the highest values (take away the the lowest value).
• 09-25-2010, 02:50 AM
dxg
Quote:

Originally Posted by al_Marshy_1981
Array = { 1, 2, -5, 6, -1, 100 } =105;
Array={100,2,-5,-1,1,6} = 105; order does not matter a jot....... summing all the elements will always give the same amount no matter what order you take when only additon and subtraction is involved. therefore like I said earlier the highest subsequence will always be the highest values (take away the the lowest value).

Array = { 100, 2, -5, -7, 1, 6 } ; maxSum = 102
Array = { 100, -5, -7, 1, 2, 6 } ; maxSum = 100
• 09-25-2010, 02:55 AM
al_Marshy_1981
Quote:

Originally Posted by dxg

Array = { 100, 2, -5, -7, 1, 6 } ; maxSum = 102
Array = { 100, -5, -7, 1, 2, 6 } ; maxSum = 100

they are both 97?? am i missing something here?
• 09-25-2010, 02:59 AM
dxg
Quote:

Originally Posted by al_Marshy_1981
they are both 97?? am i missing something here?

In a normal subsequence this would be correct; however I may not emphasized it enough you may not skip over any integers.

Array { n1, n2, n3, n4 }

regular subsequence = { n2, n4 }

my program subsequence cannot skip over an object, so to acquire n4 you would have to include n3: { n2, n3, n4 }

My apologies if I did not make this clear.
• 09-25-2010, 08:30 AM
JosAH
Can't it be done iteratively, i.e. two nested loops:

Code:

```for (int i= 0; i < array.length; i++)   for (int j= i+1; j <= array.length; j++)       // compute sum [i, j)```
... and remember i and j for maximum values of sum. Pay close attention to the loop boundaries.

kind regards,

Jos
• 09-25-2010, 05:40 PM
dxg
Yes, great thinking!

Thank you very much.