Find longest subsequence in a list

I want to write a function that finds the longest ascending sequence in a list in linear time. This seems like a really easy task but without nested for-loops I am stuck somehow. My idea was the following:

if len(L) == 0 or len(L) == 1:
    return len(L)

if all(L[i] == L[0] for i in range(len(L)-1)):
    return len(L)

left = [1] * len(L)
right = [1] * len(L)
count = 1
for i in range(len(L)-1):
    if L[i] <= L[i+1]:
        count += 1
        left[i+1] = count
    else:
        count = 1
        left[i+1] = count

count = 1
for i in range(len(L)-1, -1, -1):
    if L[i] <= L[i-1]:
        count += 1
        right[i-1] = count
    else:
        count = 1
        right[i-1] = count

idx_left = left.index(max(left))
idx_right = right.index(max(right))

if max(max(left), max(right)) == max(left) and idx_left == len(left) - 1:
    return max(left)

You can try this:

mylist=[10,9,8,10,6,5,4,3,2,3]

previous  = mylist[0]
max_sublist = [previous]
current_sublist = [previous]
increasing = True

for x in mylist[1:]:
    if increasing and previous <= x:
        current_sublist.append(x)
    elif previous >= x:
        increasing = False
        current_sublist.append(x)
    else:
        if len(current_sublist) > len(max_sublist):
            max_sublist = current_sublist[:]
        current_sublist = [previous, x]
        increasing = True
    previous = x

if len(current_sublist) > len(max_sublist):
            max_sublist = current_sublist[:]

print(f"{max_sublist=}\n{len(max_sublist)=}")

It gives:

max_sublist=[8, 10, 6, 5, 4, 3, 2]
len(max_sublist)=7

try working on the diffrences between 2 values,
I'm not sure it works for every case but it's a start in o(n),

added 1 to the resault in the end cause it's counting comparisons so the last value will not be counted

def sequance(seq):
max_len = 0
current_len = 0
going_down = False
for i in range(len(seq)-1):
    if seq[i] == seq[i+1]:
        current_len += 1
        if max_len < current_len:
            max_len = current_len
        continue
    if seq[i] < seq[i+1]:
        if going_down:
            current_len = 1
            going_down = False
            continue
        else:
            current_len +=1
            if max_len < current_len:
                max_len = current_len
            continue

    if seq[i] > seq[i+1]:
        if going_down:
            current_len += 1
            if max_len < current_len:
                max_len = current_len
            continue
        else:
            going_down = True
            current_len += 1
            if max_len < current_len:
                max_len = current_len
return max_len + 1

[10, 9, 8, 10, 6, 5, 4, 3, 2, 3] #    7
[4, 5, 3, 2, 1, 3, 6, 4, 7] #    5
[10, 9, 8, 7, 6, 5, 4, 3, 2, 3] #    9
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] #    10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] #    10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] #    19
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] #    10
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] #    10
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1] #    9
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1] #    9
[1, 1, 1, 0, 0, 0, 0, 0, 0, 2] #    9

You can consider the increasing/decreasing state of grouped identical values, and keep track of the previous length. The complexity is O(n) with a single pass on the input:

from itertools import groupby

def sequence(lst):
    max_len = 0
    prev = float('nan')
    prev_len = 0
    running_len = 0
    increasing = False
    for k, g in groupby(lst):
        L = len(list(g))
        if k < prev:
            running_len += L
            increasing = False
        else:
            if increasing:
                running_len += L
            else:
                max_len = max(max_len, running_len)
                running_len = L + prev_len
                increasing = True
        prev = k
        prev_len = L

    return max(max_len, running_len)

sequence([10,9,8,10,6,5,4,3,2,3]) 

Output: 7

NB. itertools.groupby is just a convenience to avoid having to handle the successive identical values. But you don't have to use it and can track those yourself.

Other examples:

sequence([10, 9, 8, 10, 6, 5, 4, 3, 2, 3])
#7               *   *  *  *  *  *  *

sequence([4, 5, 3, 2, 1, 3, 6, 4, 7])
#5        *  *  *  *  *

sequence([10, 9, 8, 7, 6, 5, 4, 3, 2, 3])
#9         *  *  *  *  *  *  *  *  *

sequence([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
#10        *  *  *  *  *  *  *  *  *  *

sequence([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
#10       *  *  *  *  *  *  *  *  *   *

sequence([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
#19       *  *  *  *  *  *  *  *  *   *  *  *  *  *  *  *  *  *  *

sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
#10       *  *  *  *  *  *  *  *  *  *

sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 1])
#10       *  *  *  *  *  *  *  *  *  *

sequence([1, 0, 0, 0, 0, 0, 0, 0, 0, 1])
#9           *  *  *  *  *  *  *  *  *

sequence([1, 1, 0, 0, 0, 0, 0, 0, 0, 1])
#9        *  *  *  *  *  *  *  *  *

sequence([1, 1, 1, 0, 0, 0, 0, 0, 0, 2])
#9        *  *  *  *  *  *  *  *  *

refactoring the code

This is the exact same logic as above but tests have been combined, intermediate variables removed, etc.

from itertools import groupby

def sequence(lst):
    max_len = prev_len = running_len = 0
    prev = float('nan')
    decreasing = False
    for k, g in groupby(lst):
        if k < prev:
            decreasing = True
        elif decreasing:
            max_len = max(max_len, running_len)
            running_len = prev_len
            decreasing = False
        prev = k
        prev_len = len(list(g))
        running_len += prev_len

    return max(max_len, running_len)