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