You are given a sequence S of integers (not necessarily positive). The number of integers is n. The problem is to find the consecutive subsequence of S with maximum sum. Here, Consecutive means that you are not allowed to skip numbers. For example if the input was 12, 14, 1, 23, 6, 22, 34, 13 the output would be 1, 23, 6, 22.

Now give a linear time dynamic programming algorithm for this problem.

You should explain why a naive recursive solution is not possible. That is, figure out why knowing the i-th number, and the maximum consecutive sum of the first i 1 numbers, is not enough to compute the maximum consecutive sum of the first i numbers. This should give you a big hint how to strengthen the inductive hypothesis