数据结构与算法分析 java Weiss的java数据结构与问题解决

Weiss的java数据结构与问题解决  

　　import java util Random;

　　public final class MaxSumTest

　　{

　　static private int seqStart = ;

　　static private int seqEnd = ;

　　/**

　　* Cubic maximum contiguous subsequence sum algorithm

　　* seqStart and seqEnd represent the actual best sequence

　　*/

　　public static int maxSubSum ( int [ ] a )

　　{

　　int maxSum = ;

　　for( int i = ; i < a length; i++ )

　　for( int j = i; j < a length; j++ )

　　{

　　int thisSum = ;

　　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 maxSubSum ( int [ ] a )

　　{

　　int maxSum = ;

　　for( int i = ; i < a length; i++ )

　　{

　　int thisSum = ;

　　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 maxSubSum ( int [ ] a )

　　{

　　int maxSum = ;

　　int thisSum = ;

　　for( int i = j = ; j < a length; j++ )

　　{

　　thisSum += a[ j ];

　　if( thisSum > maxSum )

　　{

　　maxSum = thisSum;

　　seqStart = i;

　　seqEnd   = j;

　　}

　　else if( thisSum < )

　　{

　　i = j + ;

　　thisSum = ;

　　}

　　}

　　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 = maxRightBorderSum = ;

　　int leftBorderSum = rightBorderSum = ;

　　int center = ( left + right ) / ;

　　if( left == right )  // Base case

　　return a[ left ] > ? a[ left ] : ;

　　int maxLeftSum  = maxSumRec( a left center );

　　int maxRightSum = maxSumRec( a center + right );

　　for( int i = center; i >= left; i– )

　　{

　　leftBorderSum += a[ i ];

　　if( leftBorderSum > maxLeftBorderSum )

　　maxLeftBorderSum = leftBorderSum;

　　}

　　for( int i = center + ; i <= right; i++ )

　　{

　　rightBorderSum += a[ i ];

　　if( rightBorderSum > maxRightBorderSum )

　　maxRightBorderSum = rightBorderSum;

　　}

　　return max ( maxLeftSum maxRightSum

　　maxLeftBorderSum + maxRightBorderSum );

　　}

　　/**

　　* Return maximum of three integers

　　*/

　　private static int max ( 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 maxSubSum ( int [ ] a )

　　{

　　return a length > ? maxSumRec( a a length ) : ;

　　}

　　public static void getTimingInfo( int n int alg )

　　{

　　int [] test = new int[ n ];

　　long startTime = System currentTimeMillis( );;

　　long totalTime = ;

　　int i;

　　for( i = ; totalTime < ; i++ )

　　{

　　for( int j = ; j < test length; j++ )

　　test[ j ] = rand nextInt( ) ;

　　switch( alg )

　　{

　　case :

　　maxSubSum ( test );

　　break;

　　case :

　　maxSubSum ( test );

　　break;

　　case :

　　maxSubSum ( test );

　　break;

　　case :

　　maxSubSum ( test );

　　break;

　　}

　　totalTime = System currentTimeMillis( ) startTime;

　　}

　　System out println( Algorithm # + alg + t

　　+ N = + test length

　　+ ttime = + ( totalTime * / i ) + microsec );

　　}

　　private static Random rand = new Random( );

　　/**

　　* Simple test program

　　*/

　　public static void main( String [ ] args )

　　{

　　int a[ ] = { };

　　int maxSum;

　　maxSum = maxSubSum ( a );

　　System out println( Max sum is + maxSum + ; it goes

　　+ from + seqStart + to + seqEnd );

　　maxSum = maxSubSum ( a );

　　System out println( Max sum is + maxSum + ; it goes

　　+ from + seqStart + to + seqEnd );

　　maxSum = maxSubSum ( a );

　　System out println( Max sum is + maxSum + ; it goes

　　+ from + seqStart + to + seqEnd );

　　maxSum = maxSubSum ( a );

　　System out println( Max sum is + maxSum );

　　// Get some timing info

　　for( int n = ; n <= ; n *= )

　　for( int alg = ; alg >= ; alg– )

　　{

　　if( alg == && n > )

　　continue;

　　getTimingInfo( n alg );

　　}

　　}