Home Java SE Tips

Java Network
 Java Forums Java Blog

Most Visited Tips
Top Rated Tips
Statistics
 Registered Users: 4116 Java SE Tips: 614 Java ME Tips: 202 Java EE Tips: 183 Other API Tips: 779 Java Applications: 298 Java Libraries: 209 Java Games: 16 Book Reviews:

 Finding Maximum Contiguous Subsequence Sum using divide-and-conquer approach
User Rating: / 81
PoorBest

Given a sequence Q of n numbers (positive and negative), the maximum subsequence of Q is the contiguous subsequence that has the maximum sum among all contiguous subsequences of Q.

The following class shows how to implement cubic, quadratic, linear-time and recursive maximum contiguous subsequence sum algorithms in Java.

 ``` public final class MaxSumTest {     static private int seqStart = 0;     static private int seqEnd = -1;     /**      * Cubic maximum contiguous subsequence sum algorithm.      * seqStart and seqEnd represent the actual best sequence.      */     public static int maxSubSum1( int [ ] a )     {         int maxSum = 0;         for( int i = 0; i < a.length; i++ )             for( int j = i; j < a.length; j++ )             {                 int thisSum = 0;                 for( int k = i; k <= j; k++ )                     thisSum += a[ k ];                 if( thisSum > maxSum )                 {                     maxSum   = thisSum;                     seqStart = i;                     seqEnd   = j;                 }             }         return maxSum;     }     /**      * Quadratic maximum contiguous subsequence sum algorithm.      * seqStart and seqEnd represent the actual best sequence.      */     public static int maxSubSum2( int [ ] a )     {         int maxSum = 0;         for( int i = 0; i < a.length; i++ )         {             int thisSum = 0;             for( int j = i; j < a.length; j++ )             {                 thisSum += a[ j ];                 if( thisSum > maxSum )                 {                     maxSum = thisSum;                     seqStart = i;                     seqEnd   = j;                 }             }         }         return maxSum;     }     /**      * Linear-time maximum contiguous subsequence sum algorithm.      * seqStart and seqEnd represent the actual best sequence.      */     public static int maxSubSum3( int [ ] a )     {         int maxSum = 0;         int thisSum = 0;         for( int i = 0, j = 0; j < a.length; j++ )         {             thisSum += a[ j ];             if( thisSum > maxSum )             {                 maxSum = thisSum;                 seqStart = i;                 seqEnd   = j;             }             else if( thisSum < 0 )             {                 i = j + 1;                 thisSum = 0;             }         }         return maxSum;     }     /**      * 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 );         int maxRightSum = maxSumRec( a, center + 1, right );         for( int i = center; i >= left; i-- )         {             leftBorderSum += a[ i ];             if( leftBorderSum > maxLeftBorderSum )                 maxLeftBorderSum = leftBorderSum;         }         for( int i = center + 1; i <= right; i++ )         {             rightBorderSum += a[ i ];             if( rightBorderSum > maxRightBorderSum )                 maxRightBorderSum = rightBorderSum;         }         return max3( maxLeftSum, maxRightSum,                      maxLeftBorderSum + maxRightBorderSum );     }     /**      * Return maximum of three integers.      */     private static int max3( int a, int b, int c )     {         return a > b ? a > c ? a : c : b > c ? b : c;     }     /**      * Driver for divide-and-conquer maximum contiguous      * subsequence sum algorithm.      */     public static int maxSubSum4( int [ ] a )     {         return a.length > 0 ? maxSumRec( a, 0, a.length - 1 ) : 0;     }     /**      * Simple test program.      */     public static void main( String [ ] args )     {         int a[ ] = { 4, -3, 5, -2, -1, 2, 6, -2 };         int maxSum;         maxSum = maxSubSum1( a );         System.out.println( "Max sum is " + maxSum + "; it goes"                        + " from " + seqStart + " to " + seqEnd );         maxSum = maxSubSum2( a );         System.out.println( "Max sum is " + maxSum + "; it goes"                        + " from " + seqStart + " to " + seqEnd );         maxSum = maxSubSum3( a );         System.out.println( "Max sum is " + maxSum + "; it goes"                        + " from " + seqStart + " to " + seqEnd );         maxSum = maxSubSum4( a );         System.out.println( "Max sum is " + maxSum );     } }```

### Related Tips

Page 1 of 0 ( 0 comments )

Name (required)

E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)

Comment Enable HTML code : Yes No