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)
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