Find longest subsequence in a list in O(n)-CodePudding

I want to write a function that finds the longest sequence a_0 <= a_1 <= ... <= a_k >= a_(k 1) >= ... >= a_n 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)
elif max(max(left), max(right)) == max(right) and idx_right == 0:
    return max(right)

if idx_left == idx_right:
    return max(left)   max(right) - 1
elif idx_left < idx_right:
    return max(left)   max(right[idx_left:])
else:
    return max(left[:idx_right])   max(right)
    
return max(max(left)   max(right[idx_left:]), max(right)   max(left[:idx_right]))

This works sometimes but i found several cases that will produce an incorrect output. Do you have any idea how to fix this?

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


# These cases are not working yet
print(sequence([1,0,0,0,0,0,0,0,0,1])) # 10
print(sequence([1,1,0,0,0,0,0,0,0,1])) # 10
print(sequence([1,1,1,0,0,0,0,0,0,2])) # 9

CodePudding user response：

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

CodePudding user response：

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

CodePudding user response：

You can consider the increasing/decreasing state of grouped identical values, and keep track of the previous length:

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

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