Acontiguous subsequence of a list s is a subsequence made up of consecutive elements of s. for instance, if s is

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 a linear-time 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. (Hint: For each j =1; 2; : : : ; ng, consider contiguous subsequences ending exactly at position j.) Here is my solution in Python 3. Notes: * If more than one subset equal the maximum value, only the first is returned. * The manner of inputting the list was not specified. The list is hardcoded. * The output was not formatted exactly to specifications. * The preceding points were not improved upon in order to keep the code simple. python 3 -- leading dots are spaces for indentation def maxSubSeq(seq): max_sum = 0 max_subseq = [] for start in range(len(seq)): for end in range(start+1, len(seq)+1): subseq = seq[start:end] total = sum(seq[start:end]) if total > max_sum: max_sum = total max_subseq = subseq return(max_subseq) seq=[5, 15, -30, 10, -5, 40, 10] print(maxSubSeq(seq)) Output: [10, -5, 40, 10]