CS3383 (Winter 2021) - Assignment 6 3 2. (5 marks) (Adapted from Dasgupta et al., Question 6.1) A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For instance, if S is -1, -3, 6, -2,1, -8, -4,5 then -3,6, -2 is a contiguous subsequence, but 6,1, -8 is not. Give a linear-time (O(n)) dynamic programming algorithm for the following task: Input: A list of numbers a1, 22, ...,an Output: The contiguous subsequence of minimum sum (Note: The empty sequence is a subsequence of any sequence and has a sum of zero.) For the example above, the answer would be -2,1,-8, -4, with a sum of -13. For an input of 1, 2, 5, 9, 12, 6, the answer would be the empty sequence, with a sum of 0. (Hint: For each je {1, 2, ... ,n}, consider contiguous subsequences that end exactly at position j, but consider the empty sequence as well. In the original example above, the minimum-sum contiguous subsequence ending at the second position would be -1, -3, with a sum of 4. The minimum-sum contiguous subsequence ending at the third position would be the empty subsequence, with a sum of 0.)