连续子序列最大和算法

tchlinux

数组a中存放K个整数的序列{N1,N2,…,Nk,},其任意连续子序列可表示为{Ni,Ni+1,…,Nj,},其中1连续子序列是所有连续子序列中元素和最大的一个.例如给定序列{-2,11,-4,13,-5,-2},其最大连续子序列为{11,-4,13},最大和为20,子序列长度为3.
问题: 编写函数maxsubstr,其功能是求最大连续子序列的最大和，以及最大连续子序列的长度，函数的返回值表示求得的最大和。
import java.util.Random;
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  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  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  maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
            else if( thisSum  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  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;
    }
    public static void getTimingInfo( int n, int alg )
    {
        int [] test = new int[ n ];
        long startTime = System.currentTimeMillis( );;
        long totalTime = 0;
        int i;
        for( i = 0; totalTime = 1; alg-- )
            {
                if( alg == 1 && n > 50000 )
                    continue;   
                getTimingInfo( n, alg );
            }
    }
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/67780/showart_2072602.html