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:

UVa 10684 - The Jackpot