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 1) the pseudocode of your recursive algorithm in the prologue docstrings, 2) the explanation of its complexity in the prologue docstrings, 3) a Python function max_subseq that implements your algorithm. 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.