Python Programming

20

Longest sorted subsequence. Write a function longest_monotone ) that returns the length and starting index of the longest contiguous sorted subsequence of a given list a. The subsequence can be in either ascending or descending order. For example, given input [ 0, 10, 5,-1, 3, 6 1 your function should return (3, 1), since the longest sorted (in this case, descending) subsequence is 10, 5, -1. For input [ -1, 5, 1, 0, 5 ] you should return (4, 1) (corresponding to the ascending subsequence -5, -1, 0, 5). You can assume that there are no consecutive equal values in the sequence. How would your solution change if consecutive equal values were allowed? Remark. The term "subsequence" typically refers to a non-contiguous sequence; e.g., the list [2,5,7, 8] is a subsequence of [1,2,3,4, 5, 6,7,8, 9]. However, in this problem we abuse the term to refer to contiguous subsequences only, which would perhaps be better called "segments" [ Hint: You should at least check that your code works for [t0, 0, 0], [1, 2, 3], 3, 2, 11, [0, 1, 0, 1, 0, 1], and [1, 2, 3, 2, 1, 0, 1]. If you modify your solution to also deal with possible constant consecutive pairs, then you should check that your code works with at least [ 1, 2 , 3, 3?2, 2 , 1 , 0, 0, 1 ]