﻿ Weiss的java數據結構與問題解決_電腦知識網

# Weiss的java數據結構與問題解決

2013-11-23 19:33:11  來源: Java核心技術

import javautilRandom;

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 < alength; i++ )

for( int j = i; j < alength; 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 < alength; i++ )

{

int thisSum = ;

for( int j = i; j < alength; j++ )

{

thisSum += a[ j ];

if( thisSum > maxSum )

{

maxSum = thisSum;

seqStart = i;

seqEnd   = j;

}

}

}

return maxSum;

}

/**

* Lineartime 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 < alength; 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[leftright]

* 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 divideandconquer maximum contiguous

* subsequence sum algorithm

*/

public static int maxSubSum( int [ ] a )

{

return alength > ? maxSumRec( a alength ) : ;

}

public static void getTimingInfo( int n int alg )

{

int [] test = new int[ n ];

long startTime = SystemcurrentTimeMillis( );;

long totalTime = ;

int i;

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

{

for( int j = ; j < testlength; j++ )

test[ j ] = randnextInt( ) ;

switch( alg )

{

case :

maxSubSum( test );

break;

case :

maxSubSum( test );

break;

case :

maxSubSum( test );

break;

case :

maxSubSum( test );

break;

}

totalTime = SystemcurrentTimeMillis( ) startTime;

}

Systemoutprintln( Algorithm # + alg + \t

+ N = + testlength

+ \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 );

Systemoutprintln( Max sum is + maxSum + ; it goes

+ from + seqStart + to + seqEnd );

maxSum = maxSubSum( a );

Systemoutprintln( Max sum is + maxSum + ; it goes

+ from + seqStart + to + seqEnd );

maxSum = maxSubSum( a );

Systemoutprintln( Max sum is + maxSum + ; it goes

+ from + seqStart + to + seqEnd );

maxSum = maxSubSum( a );

Systemoutprintln( 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 );

}

}

}

From:http://tw.wingwit.com/Article/program/Java/hx/201311/27079.html