Bentley’s Treatment of the Maximum Sum Subsequence Problem

I thoroughly enjoyed the treatment given to this problem by Jon Bentley.

In particular, the section on “Principles” was such an exciting read – it shows some of the tricks used in algorithm design :

• Save state to avoid recomputation
• Preprocess state into data structures 
• Divide and conquer algorithms
• Scanning algorithms
• Cumulatives 
• Lower bounds
• Sorting (my humble addition to the list)

References:

• http://wordaligned.org/articles/the-maximum-subsequence-problem
• Programming Pearls E-Book

• Programming pearls: algorithm design techniques by Bentley

• Programming pearls: abstract data types by Bentley
• Fast Algorithms for Sorting and Searching Strings by Bentley