finding longuest sequence of integers when removing one

Question

I am working on a problem where i would need to find the longest subsequence of integers when removing a maximum of only one value in the original sequence. The output is the length of subsequence.

like INPUT 2 3 4 5 5 6 4 5 then OUTPUT 5 (cause when you could remove a 5, the subsequence would be 2 3 4 5 6)

like INPUT 2 3 4 4 4 5 6 7 then OUTPUT 4 (for this there is no need to remove an integer and the max subsequence is 4 5 6 7)

Answer 1

This is a O(n) implementation which manages your examples correctly, but it shoud be checked on some more cases.

def incr_subseq(ls):
    best = 0
    current = 1
    skipped = False
    for i in range(1, len(ls)):
        if ls[i] > ls[i-1]:
            current += 1
        else:
            #breaks the subseq, can we skip it?
            if i < len(ls)-1 and not skipped:
                if ls[i+1] > ls[i-1] or i > 1 and ls[i+1] > ls[i-2]:
                    skipped = True
                    continue
            if current > best:
                best = current
            #start a new subseq
            current = 1
            skipped = False
    if current > best:
        return current
    return best

incr_subseq([1, 4, 2, 3, 5, 6, 7])
6
incr_subseq([2, 3, 4, 5, 5, 6, 4, 5])
5
incr_subseq([2, 3, 4, 4, 4, 5, 6, 7])
4

Answer 2

You can use this python method to achieve this

def longest_subsequence(seq):
    max_length = 0  
    for i in range(len(seq)):
        subseq_set = set()
        subseq_length = 0  
        remove_count = 0  
        for j in range(i, len(seq)):
            if seq[j] not in subseq_set:
                subseq_set.add(seq[j])
                subseq_length += 1
            else:
                remove_count += 1
            if remove_count > 1:
                break
        max_length = max(max_length, subseq_length)  # Update the maximum length
    return max_length
input1 = [2, 3, 4, 5, 5, 6, 4, 5]
input2 = [2, 3, 4, 4, 4, 5, 6, 7]
output1 = longest_subsequence(input1)
output2 = longest_subsequence(input2)
print("Output 1:", output1) 
print("Output 2:", output2)