Maximum Subsequence Sum

Algorithms: A Top-Down Approach (R. Howell) describes five algorithms (four in Chapter 1 and one in Chapter 3) for solving the maximum subsequence sum problem, and reports the results of timing tests of implementations of each of them. This page gives the code used to conduct these tests.

Algorithm Implementations

All five algorithms were coded in the JavaTM language. A driver was then written to generate random test data and to run a selected algorithm on the given data set. When the algorithm completes, the program reports the time required by the algorithm.

Running the Program

If you have Java Web Start installed (it is included with the Java Runtime Environment, versions 1.4 and later), you may launch the program by clicking here. Java Web Start provides a safe way for running downloaded programs, as it prevents the program from accessing resources such as your file system. Java Web Start will also keep a copy on your system, so that you can run the program without returning to this web page - simply open Java Web Start and launch the application. It will attempt to determine if a newer version is available, then run the program.

Generating data

Upon pressing the "Generate Data..." button, you will be presented with a GUI for providing the parameters for generating data. You may re-examine these parameters at any time by pressing the "Generate Data..." button. If you don't wish to generate a new data set, simply press the "Cancel" button.

Viewing the data

Upon pressing the "View Data..." button, a window lising the elements of the array will be shown. If you would like to save these values to a file, you can use your system's copy/paste facility to copy them to a text editor. For a large data set, attempting to view the data may generate a java.lang.OutOfMemoryError.

Selecting an algorithm

One of the five algorithms can be selected using the drop-down menu labeled "Algorithm:".

Running an algorithm

Pressing the "Run Algorithm" button will cause the selected algorithm to be run on the current data set. When the algorithm finishes, the maximum subsequence sum and the time required will be displayed.

Caution: There is no facility within the program for aborting an algorithm. As a result, it may be difficult (especially on a single-CPU machine) to stop execution if the algorithm is taking a long time. Furthermore, the running times of some of these algorithms increase rather dramatically. A recommended approach is to start a given algorithm on a data set of size 100, then as long as the running time is no more that 0.1 seconds, keep multiplying the size by 10. Once the running time exceeds 0.1 seconds, and as long as it is no more than 15 seconds, keep multiplying the size by 2. Proceeding in this way should keep all execution times below 2 minutes.

Note also that it is normal for MaxSumTD to generate a java.lang.StackOverflowError on arrays of moderate size. This algorithm is tail-recursive, and hence uses a lot of stack space.

Source Code

To obtain the entire source code, you may downloade and unpack the zip archive The individual files are as follows:

Copyright © 2003, 2007, Rod Howell.

Valid HTML 4.01!
Valid CSS!

Sun, Sun Microsystems, the Sun Logo, and Java are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.