In programming contests, some algorithms and techniques get more emphasis than they do in school or in professional programming work. One such technique is dynamic programming. CP3 has this to say about dynamic programming:
This technique was not known before 1940s, nor frequently used in ICPCs or IOIs before mid 1990s, but it is considered a deﬁnite prerequisite today. As an illustration: There were ≥3 DP problems (out of 11) in the recent ICPC World Finals 2010.
As you might expect for such a popular competitive programming topic, uHunt has twenty-one starred problems, divided into seven sub-categories, for dynamic programming practice. As I make my way through that list, I’ll be writing about a selection of these problems. Today I’ll cover the first one, UVa 787: Maximum Sub-sequence Product.