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