QUESTION 2 (25 Marks) Let S = {x1,x2,..., Xn} be a non-empty sequence of integers. Give an O(n) recursive divide-and- conquer algorithm to find the largest possible sum of a subsequence of consecutive items in S. Example: S = [10, 20,3,4,5,-1,-1,12, -3,1] has the largest sum 22 (of subsequence [3,4,5,-1,-1,12]). S = [-1,2, 5] has the largest subsequence sum 2 S = [3, -2,4, -6,2] has the largest subsequence sum 5 In your T2-2.py file, provide 1) (7 marks) the pseudocode of your recursive algorithm in the prologue docstrings, 2) (3 marks) the explanation of its complexity in the prologue docstrings, 3) (15 marks) a Python function max_subseq that implements your algorithm. Your program will be marked on correctness (8 marks), style and logic (4 marks), and comments and readability (3 marks). Hint: Assume you can solve the problem for a sequence of n 1 integers. Think about what you need to go from a solution on a sequence of n - 1 integers to a solution on a sequence of one additional integer