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)


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s