Question

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

Answer 1

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] _____