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: abstract data types by Bentley
- Fast Algorithms for Sorting and Searching Strings by Bentley
Advertisements
