Python - 测量列表中某个值的最长子序列，并具有容错性

Question

给定一个整数列表 [0,0,0,1,1,0,2,2,0,1,0,0,2,1,2,2,2,2,1,...] ，我需要计算其中 x% 的元素为 n 的元素的最长子序列，即存在一个容差，即包含小于 1 - x% 值的子序列仍被视为 n 的完整子序列。

我使用以下单行来获得所有值为 n 的最长子序列，但我不知道从哪里开始:

longest_subsequence_0 = max((len(l) for n, l in itertools.groupby(list) if n == 0))

如果有人能引导我朝着正确的方向前进，我将不胜感激:D

Answer 1

只是一个滑动窗口改变大小并计算百分比。如果高于阈值，如果此窗口大小大于先前存储的窗口大小，则记录窗口大小。

def longest_sub(list, n, threshold):
    largest_window = 0
    for i in range(len(list)+1): # from i 
        for j in range(i+1,len(list)+1): # to j
            window_len = len(list[i: j]) # store window size
            if window_len > largest_window: # if inspected window > largest found yet
                if list[i:j].count(n)/window_len*100 > threshold: # if percentage above threshold
                    largest_window = window_len # new largest_window
    return largest_window

longest_sub([0,0,0,1,1,0,2,2,0,1,0,0,2,1,2,2,2,2,1], 0, 30) # 9 
longest_sub([0,0,0,1,1,0,2,2,0,1,0,0,2,1,2,2,2,2,1], 0, 80) # 3