A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S$.$ For

instance, if S is $1,5,10,11,20,5$ then $5,10,$ is a contiguous subsequence but $5,11,20$ is not.

Give a linear$-$time algorithm for the following task:

Input: A list of numbers S $=$ a$1,$ a$2,...,$ an$.$

Output: The contiguous subsequence of maximum sum $($a subsequence of length zero has sum zero$).$

For the preceding example, the answer would be $11,20$ with a sum of $31.$ Write the subproblem

definition, recurrence relation, base case with explanation, and analyze the running time.

CMPSC $465,$ Fall $2024,$ HW $111$