next up previous contents index Search
Next: Analysis Up: 0.5.1 Maximum Consecutive Subsequence Previous: 0.5.1 Maximum Consecutive Subsequence Divide and Conquer Solution

The premise behind the first solution to the maximum subsequence problem is that any set can be divided into two sets of one-half the aggregate size. The maximum subsequence of the original set must: be entirely on the left half of the division, be entirely on the right half of the division, or span the middle of the division.

Scott Gasch