熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> Java編程 >> 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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.