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 Java^TM 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.

Size of the array: The number of elements in the array to be passed to the algorithm(s). This can be any nonnegative integer less than 2³¹ = 2,147,483,648 (note, however, the caution below). In most cases, the Java Virtual Machine will not have a large enough heap to store an array whose size is near the maximum allowable size. If you try to generate a data set that will not fit in the heap, you will generate a java.lang.OutOfMemoryError, and your previous data set will not be replaced. You may be able to generate a somewhat larger data set by first generating a data set of size 0 to cause the program to discard your current data set.
Max absolute value: The upper limit on values generated. This can be any positive integer less than 2³⁰ = 1,073,741,824. The lower limit will be the negative of this value. Note that if this value is too large, overflow can cause the different algorithms to produce as many as 3 different results (try, for example, a data set of size 10, a max of 1,000,000,000, and a seed of 7); however, this should not affect the timing. Choosing a value no more than 10,000 should avoid overflow.
Seed (optional): The seed for the random number generator. This can be any integer that is at least -2³¹ and less than 2³¹, or it can be left blank. Choosing a seed is useful if you want to use the same data set on different occasions. If you don't choose a seed, each data set you generate will probably be different.

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 maxsum-src.zip. The individual files are as follows:

The five maximum subsequence sum algorithms:
Other files:
- MaxSum - the main driver and GUI
- GenerateDialog - the dialog for obtaining parameters for test data generation
- MaxSumInterface - interface implemented by each of the five classes containing maximum subsequence sum algorithms

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