6 ms·
This way of thinking also makes it easy to derive the max-sum algorithm from Programming Pearls: We have to compute max-sum for (x:xs), so first solve it for x
by ssp 15y ago
This way of thinking also makes it easy to derive the max-sum algorithm from Programming Pearls:
We have to compute max-sum for (x:xs), so first solve it for xs. If the max-sum is within xs, we are done; if not, it somehow involves x. To find out, the recursion has to also return the best sum of the beginning of the list.
A small case analysis can find out what the new max-sum is: x, x + max-begin(xs), or max-sum(xs)? And the new max-begin is either x or x + max-begin (xs).
The naive recursive implementation will require linear space though, so there is an extra step to find out how to eliminate the recursion.
- psykotic 15y agoYes, Manber derives the linear-time algorithm for the maximal subsum problem exactly like that in his textbook. As you say, if x is involved in a maximal subsum, it must extend the tail's maximal prefix sum, so you return that in addition to the maximal subsum. Regarding recursion vs iteration, Manber generally develops the right induction hypothesis gradually, using informal language ("remove the element and solve the smaller problem") in the process, and only turns that into a precise algorithm once the final induction hypothesis has been found, so he doesn't present the recursion elimination as a separate step. That works well pedagogically. His main idea is to guide the student's intuitions rather than formally derive a program that's correct by construction the way someone like Richard Bird might have done it. (Bird has an interesting derivation of the maximal subsum algorithm that begins with the brute-force algorithm written as a combinator-based functional program and gradually transforms it in a correctness-preserving way using program calculation techniques until arriving at the fast linear-time program.)