CS Algorithms:

Q:

***Correct answer will receive a upvote, wrong answer will receive a downvote. Thank you!

4. (10 points) A contiguous subsequence of a list S is a subsequence made up of consecutive elements of S. For instance, if S is 5,15,30,10,5,40,10, then 15,30,10 is a contiguous subsequence but 5,15,40 is not. Give an algorithm for the following task: Input: A list of numbers, a1,a2,,an. Output: The contiguous subsequence of maximum sum (a subsequence of length zero has sum zero). For the preceding example, the answer would be 10,5,40,10, with a sum of 55 . Notice that you will get a different score if your algorithm meets a different time complexity requirement. The max score which you can obtain is given for each requirement. - Basic requirement: O(n2) (max score: 6 points) - Medium requirement: O(nlogn) (max score: 8 points) - Advanced requirement: O(n) (max score: 10 points)