Dynamic programming

A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub-solution of the problem is constructed from previously found ones. DP solutions have a polynomial complexity which assures a much faster running time than other techniques like backtracking, brute-force etc.

We will look at some dynamic programming problems from easier to harder. Solutions to these problems, as with most DP problems, take the form of a recurrence relation, a short correctness proof of the recurrence relation and a running time analysis.

Q 1: Maximum value contiguous subsequence: Given a sequence of n real numbers, a1; a2; :::; an, give an algorithm for finding a contiguous subsequence for which the value of the sum of the elements is maximized.

Solution:
Recursion: We recurse on the maximum value subsequence ending at j:

With each element of M, you also keep the starting element of the sum (the same as for M(j -1) or j if you restart). At the end, you scan M for the maximum value and return it and the starting and ending indexes. Alternatively, you could keep track of the maximum value as you create M.
Running Time: M is size n and evaluating each element of M takes O(1) time for O(n) time to create M. Scanning M also takes O(n) time for a total time of O(n).