java left logo
java middle logo
java right logo
 

Home
 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 4093
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
Finding Maximum Contiguous Subsequence Sum using divide-and-conquer approach E-mail
User Rating: / 79
PoorBest 

Given a sequence Q of n numbers (positive and negative), the maximum subsequence of Q is the contiguous subsequence that has the maximum sum among all contiguous subsequences of Q.

The following class shows how to implement cubic, quadratic, linear-time and recursive maximum contiguous subsequence sum algorithms in 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 );
    }
}

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.