import java.util.Random;

public final class MaxSumTest
{

 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;
 }

 return maxSum;
 }

 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;
 }
 }

 return maxSum;
 }

 private static int maxSumRec( int [ ] a, int left, int right )
 {
 if( left == right )  // Base case
 if( a[ left ] > 0 )
 return a[ left ];
 else
 return 0;

 int center = ( left + right ) / 2;
 int maxLeftSum  = maxSumRec( a, left, center );
 int maxRightSum = maxSumRec( a, center + 1, right );

 int maxLeftBorderSum = 0, leftBorderSum = 0;
 for( int i = center; i >= left; i-- )
 {
 leftBorderSum += a[ i ];
 if( leftBorderSum > maxLeftBorderSum )
 maxLeftBorderSum = leftBorderSum;
 }

 int maxRightBorderSum = 0, rightBorderSum = 0;
 for( int i = center + 1; i <= right; i++ )
 {
 rightBorderSum += a[ i ];
 if( rightBorderSum > maxRightBorderSum )
 maxRightBorderSum = rightBorderSum;
 }

 return max3( maxLeftSum, maxRightSum,
 maxLeftBorderSum + maxRightBorderSum );
 }

 public static int maxSubSum3( int [ ] a )
 {
 return maxSumRec( a, 0, a.length - 1 );
 }

 private static int max3( int a, int b, int c )
 {
 return a > b ? a > c ? a : c : b > c ? b : c;
 }

 public static int maxSubSum4( int [ ] a )
 {
 int maxSum = 0, thisSum = 0;

 for( int j = 0; j < a.length; j++ )
 {
 thisSum += a[ j ];

 if( thisSum > maxSum )
 maxSum = thisSum;
 else if( thisSum < 0 )
 thisSum = 0;
 }

 return maxSum;
 }

 public static void main( String [ ] args )
 {
 int maxSum;
 Random r=new Random();
 int b[]=new int[10000];

 for(int i=0;i<b.length;i++)
 {
 b[i]=r.nextInt()%100;
 System.out.println(b[i]);
 }

 double time2=System.currentTimeMillis();
 maxSum = maxSubSum2( b );
 System.out.println( "Maksimum Toplam " + maxSum +" süre "+(System.currentTimeMillis()-time2));
 double time3=System.currentTimeMillis();
 maxSum = maxSubSum3( b );
 System.out.println( "Maksimum Toplam " + maxSum +" süre "+(System.currentTimeMillis()-time3));
 double time4=System.currentTimeMillis();
 maxSum = maxSubSum4( b );
 System.out.println( "Maksimum Toplam " + maxSum +" süre "+(System.currentTimeMillis()-time3));

 double time1=System.currentTimeMillis();
 maxSum = maxSubSum1( b);
 System.out.println( "Maksimum Toplam " + maxSum +" süre "+(System.currentTimeMillis()-time1));
 }
}

Süreler ms cinsindendir.

Random atanmış 1000 elemanlı dizi için veriler
Maksimum 2 Toplam 873 süre 1
Maksimum 3 Toplam 873 süre 1
Maksimum 4 Toplam 873 süre 1
Maksimum 1 Toplam 873 süre 257

Random atanmış 2000 elemanlı dizi için veriler

Maksimum 2 Toplam 4996 süre 4
Maksimum 3 Toplam 4996 süre 1
Maksimum 4 Toplam 4996 süre 1
Maksimum 1 Toplam 4996 süre 2054

Random atanmış 5000 elemanlı dizi için veriler

Maksimum 2 Toplam 4408 süre 21
Maksimum 3 Toplam 4408 süre 1
Maksimum 4 Toplam 4408 süre 1
Maksimum 1 Toplam 4408 süre 33952

Random atanmış 10000 elemanlı dizi için veriler

Maksimum 2 Toplam 2748 süre 96
Maksimum 3 Toplam 2748 süre 1
Maksimum 4 Toplam 2748 süre 2
Maksimum 1 Toplam 2748 süre 248688

Not: Maxsum metodlarının kodları adresinden alınmıştır.


Yazar : Emrah Kahraman

Bilgisayar Mühendisi

Java Algoritma Analizi MaxSum (Maksimum Toplam) Testi Yazısı için Yorum Yapabilirsiniz

Kan Bağışı
Sponsor
Alexa
Hakkımda
Bağlantılar