find the longest sorted sequence in a list of numbers in python

One way to find the longest sorted sequence in a list of numbers in Python is by iterating over the list of numbers and keeping track of the longest sorted subsequence found so far. Here's an implementation of this approach:

main.py
def longest_sorted_sequence(numbers):
    longest_seq = []
    cur_seq = [numbers[0]]
    for num in numbers[1:]:
        if num >= cur_seq[-1]:
            cur_seq.append(num)
        else:
            if len(cur_seq) > len(longest_seq):
                longest_seq = cur_seq
            cur_seq = [num]
    if len(cur_seq) > len(longest_seq):
        longest_seq = cur_seq
    return longest_seq
398 chars
14 lines

Here, numbers is the list of numbers, and longest_sorted_sequence is a function that returns the longest sorted subsequence of numbers.

We start by initializing two empty lists: longest_seq, which will contain the longest sorted sequence found so far, and cur_seq, which will contain the current sorted sequence being considered.

We iterate over numbers[1:] (skipping the first number), and for each number num, we check if it is greater or equal to the last number in cur_seq. If it is, we add num to cur_seq. Otherwise, we know that cur_seq is no longer sorted, so we compare its length to the length of longest_seq. If cur_seq is longer, we set longest_seq to cur_seq. We then reset cur_seq to a new list containing only num.

Finally, we check if cur_seq is longer than longest_seq. If it is, we update longest_seq one last time before returning it.

Here's an example usage of the function:

main.py
>>> numbers = [1, 2, 3, 2, 1, 4, 5, 6, 3, 2, 1]
>>> longest_sorted_sequence(numbers)
[1, 4, 5, 6]
98 chars
4 lines

In this case, the longest sorted subsequence is [1, 4, 5, 6].

gistlibby LogSnag