next up previous contents index Search
Next: 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.

Scott Gasch