## Tuesday, July 22, 2014

### a bit of dp : Maximum Sum Subsequence (Classical Dynamic Programming)

Problem Statement:
Given a sequence of numbers $$S = a_1, a_2, \ldots, a_n$$, find the maximum sum possible for a consecutive subsequence in $$S$$.

Eg:
S = 2, 9, -4, 1, 0, -6, 7
Maximum subsequence: {2, 8}, maximum sum = 10

This problem can be solved in many ways:
1. Divide and conquer, cut the sequence by half and recursively find the max-sum subsequence of the left and right section, and comparing the result with the subsequence containing the middle element of the original subsequence. This results in the following relationship: $$T(N) = 2T(N/2) + O(N)$$, which by master's theorem, we know that $$T(N) = O(N\log{N})$$.

2. Using Bottom-Up Dynamic Programming! Keep 2 variables trail and max-sum. For every $$a_i$$, we check whether $$\text{trail} + a_i$$ is more than 0. If so, we update trail = $$\text{trail} + a_i$$, and check if trail is bigger than current max-sum, if so we update max-sum as well. When we reach the end of the subsequence, we will get the max-sum of the sequence as well.

Example problem: