Maximum subsequence

[dxg]

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 }

/**
     * 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

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

[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.

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

[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.

[dxg]

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.

/**
 * 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

[dxg]

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

[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).

[dxg]

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).

How about this,

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

[al_Marshy_1981]

How about this,

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?

[dxg]

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.

[JosAH]

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

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

[dxg]

Yes, great thinking!

Thank you very much.