Design & Analysis of Algorithm

Problem 1, (25%) A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For example, if S is 5, 15, -30, 10, -5, 40, 10, then 15, -30, 10 is a contiguous subseqence but 5, 15, 40 is not. Give a linear-time algorithm for the following task: Input: A list of numbers, a1, a2, ,an. Output: The contiguous subsequence of the maximum sum