1. Member Join Date
Sep 2010
Posts
10
Rep Power
0

## 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 }

Java 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```
Last edited by dxg; 09-25-2010 at 01:16 AM.  Reply With Quote

2. ## What help are you looking for? Do you have any specific java programming questions?

What is the "// PUT CODE HERE ******************" comment for?
What code do you want there?  Reply With Quote

3. Member Join Date
Sep 2010
Posts
10
Rep Power
0

## 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.  Reply With Quote

4. ## 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?  Reply With Quote

5. Senior Member Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
11

## 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.
Last edited by al_Marshy_1981; 09-25-2010 at 02:22 AM.  Reply With Quote

6. Member Join Date
Sep 2010
Posts
10
Rep Power
0

##  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?

Java 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```
Last edited by dxg; 09-25-2010 at 02:26 AM.  Reply With Quote

7. Member Join Date
Sep 2010
Posts
10
Rep Power
0

##  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  Reply With Quote

8. Senior Member Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
11

## 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).  Reply With Quote

9. Member Join Date
Sep 2010
Posts
10
Rep Power
0

##  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  Reply With Quote

10. Senior Member Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
11

##  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?  Reply With Quote

11. Member Join Date
Sep 2010
Posts
10
Rep Power
0

##  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.  Reply With Quote

12. ## Can't it be done iteratively, i.e. two nested loops:

Java 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  Reply With Quote

13. Member Join Date
Sep 2010
Posts
10
Rep Power
0

## Yes, great thinking!

Thank you very much.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•