Next: 0.5.1.1 Divide and Conquer
Up: 0.5 Miscellaneous Algorithms
Previous: 0.5 Miscellaneous Algorithms
0.5.1 Maximum Consecutive Subsequence
Given a sequence of numbers, how can the subsequence of greatest (or
least) value be determined? In this section two efficient algorithms
for finding maximum consecutive subsequences are explored and
analyzed. Before these methods can be presented, though, a precise
understanding of the problem is essential.
Imagine a series of n numbers
(x1, x2, x3, x4, ... xn) called
set S. The following algorithms will find the subset S' of set
S such that the sum of the members of set S' is greater than the
sum of numbers in any other subset of the original set S. If all
the members of S are positive then set S' will be the entire Sset. However, when negative values are included in S this problem
becomes more interesting and difficult to solve.