Results 1 to 13 of 13
Thread: Maximum subsequence
 09252010, 12:19 AM #1Member
 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; 09252010 at 01:16 AM.
 09252010, 01:54 AM #2
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?
 09252010, 01:59 AM #3Member
 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.
 09252010, 02:10 AM #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?
 09252010, 02:18 AM #5Senior Member
 Join Date
 Feb 2010
 Location
 Waterford, Ireland
 Posts
 748
 Rep Power
 5
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; 09252010 at 02:22 AM.
 09252010, 02:23 AM #6Member
 Join Date
 Sep 2010
 Posts
 10
 Rep Power
 0
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; 09252010 at 02:26 AM.
 09252010, 02:31 AM #7Member
 Join Date
 Sep 2010
 Posts
 10
 Rep Power
 0
 09252010, 02:43 AM #8Senior Member
 Join Date
 Feb 2010
 Location
 Waterford, Ireland
 Posts
 748
 Rep Power
 5
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).
 09252010, 02:50 AM #9Member
 Join Date
 Sep 2010
 Posts
 10
 Rep Power
 0
 09252010, 02:55 AM #10Senior Member
 Join Date
 Feb 2010
 Location
 Waterford, Ireland
 Posts
 748
 Rep Power
 5
 09252010, 02:59 AM #11Member
 Join Date
 Sep 2010
 Posts
 10
 Rep Power
 0
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.
 09252010, 08:30 AM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,651
 Blog Entries
 7
 Rep Power
 21
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)
kind regards,
Jos
 09252010, 05:40 PM #13Member
 Join Date
 Sep 2010
 Posts
 10
 Rep Power
 0
Similar Threads

find maximum value from for loop
By napi1234 in forum New To JavaReplies: 15Last Post: 06022010, 03:39 PM 
Maximum Minimum Values
By z6StringAssasin in forum New To JavaReplies: 2Last Post: 05092010, 12:36 AM 
Calculating Maximum and Minimum
By Ejava in forum New To JavaReplies: 6Last Post: 03012010, 04:36 PM 
maximum view depth?
By Bit2_Gosu in forum New To JavaReplies: 0Last Post: 02162009, 02:32 PM 
Maximum size of an array
By Hasan in forum New To JavaReplies: 1Last Post: 05202007, 11:11 AM
Bookmarks