Нахождение максимального смежные суммы подпоследовательности помощью разделяй и властвуй App

Учитывая последовательность Q п чисел (положительных и отрицательных), максимальная подпоследовательность Q является непрерывной последовательности, который имеет максимальную сумму между всеми смежными подпоследовательностей Q.

Следующий класс показывает, как реализовать кубический, квадратичного, линейного времени и рекурсивных максимальная сумма непрерывной последовательности алгоритмов в Java.


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 maxSubSum1int [ ] )

    {

        int maxSum = 0;



        forint i = 0; i < a.length; i++ )

            forint j = i; j < a.length; j++ )

            {

                int thisSum = 0;



                forint k = i; k <= j; k++ )

                    thisSum += a];



                ifthisSum > 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 maxSubSum2int [ ] )

    {

        int maxSum = 0;



        forint i = 0; i < a.length; i++ )

        {

            int thisSum = 0;

            forint j = i; j < a.length; j++ )

            {

                thisSum += a];



                ifthisSum > 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 maxSubSum3int [ ] )

    {

        int maxSum = 0;

        int thisSum = 0;



        forint i = 0, j = 0; j < a.length; j++ )

        {

            thisSum += a];



            ifthisSum > maxSum )

            {

                maxSum = thisSum;

                seqStart = i;

                seqEnd   = j;

            }

            else ifthisSum < )

            {

                i = j + 1;

                thisSum = 0;

            }

        }



        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 maxSumRecint [ ] a, int left, int right )

    {

        int maxLeftBorderSum = 0, maxRightBorderSum = 0;

        int leftBorderSum = 0, rightBorderSum = 0;

        int center = left + right 2;



        ifleft == right )  // Base case

            return aleft ? aleft 0;



        int maxLeftSum  = maxSumReca, left, center );

        int maxRightSum = maxSumReca, center + 1, right );



        forint i = center; i >= left; i-- )

        {

            leftBorderSum += a];

            ifleftBorderSum > maxLeftBorderSum )

                maxLeftBorderSum = leftBorderSum;

        }



        forint i = center + 1; i <= right; i++ )

        {

            rightBorderSum += a];

            ifrightBorderSum > maxRightBorderSum )

                maxRightBorderSum = rightBorderSum;

        }



        return max3maxLeftSum, maxRightSum,

                     maxLeftBorderSum + maxRightBorderSum );

    }



    /**

     * Return maximum of three integers.

     */

    private static int max3int a, int b, int )

    {

        return a > b ? a > c ? a : c : b > c ? b : c;

    }



    /**

     * Driver for divide-and-conquer maximum contiguous

     * subsequence sum algorithm.

     */

    public static int maxSubSum4int [ ] )

    {

        return a.length > ? maxSumReca, 0, a.length - 0;

    }



    /**

     * Simple test program.

     */

    public static void mainString [ ] args )

    {

        int a[ ] 4, -35, -2, -126, -};

        int maxSum;



        maxSum = maxSubSum1);

        System.out.println"Max sum is " + maxSum + "; it goes"

                       " from " + seqStart + " to " + seqEnd );

        maxSum = maxSubSum2);

        System.out.println"Max sum is " + maxSum + "; it goes"

                       " from " + seqStart + " to " + seqEnd );

        maxSum = maxSubSum3);

        System.out.println"Max sum is " + maxSum + "; it goes"

                       " from " + seqStart + " to " + seqEnd );

        maxSum = maxSubSum4);

        System.out.println"Max sum is " + maxSum );

    }

}

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>