Results 1 to 13 of 13
  1. #1
    dxg
    dxg is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

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

  2. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    16,564
    Rep Power
    23

    Default

    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?

  3. #3
    dxg
    dxg is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

    Default

    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.

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    16,564
    Rep Power
    23

    Default

    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?

  5. #5
    al_Marshy_1981 is offline Senior Member
    Join Date
    Feb 2010
    Location
    Waterford, Ireland
    Posts
    748
    Rep Power
    5

    Default

    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.

  6. #6
    dxg
    dxg is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by Norm View Post
    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.


    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.

  7. #7
    dxg
    dxg is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by al_Marshy_1981 View Post
    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

  8. #8
    al_Marshy_1981 is offline Senior Member
    Join Date
    Feb 2010
    Location
    Waterford, Ireland
    Posts
    748
    Rep Power
    5

    Default

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

  9. #9
    dxg
    dxg is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by al_Marshy_1981 View Post
    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

  10. #10
    al_Marshy_1981 is offline Senior Member
    Join Date
    Feb 2010
    Location
    Waterford, Ireland
    Posts
    748
    Rep Power
    5

    Default

    Quote Originally Posted by dxg View Post
    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?

  11. #11
    dxg
    dxg is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

    Default

    Quote Originally Posted by al_Marshy_1981 View Post
    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.

  12. #12
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    12,999
    Blog Entries
    7
    Rep Power
    19

    Default

    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

  13. #13
    dxg
    dxg is offline Member
    Join Date
    Sep 2010
    Posts
    10
    Rep Power
    0

Similar Threads

  1. find maximum value from for loop
    By napi1234 in forum New To Java
    Replies: 15
    Last Post: 06-02-2010, 03:39 PM
  2. Maximum Minimum Values
    By z6StringAssasin in forum New To Java
    Replies: 2
    Last Post: 05-09-2010, 12:36 AM
  3. Calculating Maximum and Minimum
    By Ejava in forum New To Java
    Replies: 6
    Last Post: 03-01-2010, 04:36 PM
  4. maximum view depth?
    By Bit2_Gosu in forum New To Java
    Replies: 0
    Last Post: 02-16-2009, 02:32 PM
  5. Maximum size of an array
    By Hasan in forum New To Java
    Replies: 1
    Last Post: 05-20-2007, 11:11 AM

Posting Permissions

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