A substring (or continuous subsequence) of a sequence S is a subsequence made up of consecutive positions of S. For example, if S is 5, 15, 30, 10, 5, 40, 10 then 15, 30, 10 is a substring of S but 5, 15, 40 is not. Consider the problem of finding the substring of maximum sum: Input: A sequence a1, a2, . . . , an of numbers. Output: A substring of maximum sum. Note that a substring of length 0 has sum 0.

a) Design and write (in pseudocode) a linear-time dynamic programming algorithm that solves this problem. (Note that this is to find such a substring, not just its sum.)