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^{31} = 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^{30} = 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^{31} and less than 2^{31}, 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
Copyright © 2003, 2007, Rod Howell.
Sun, Sun Microsystems, the Sun Logo, and Java are trademarks or
registered trademarks of Sun Microsystems, Inc. in the United States
and other countries.