找到包含0到0的最长子序列O(n)

Question

我在面试中遇到了一个问题,我找不到最佳解决方案(而且这很令人沮丧)

所以你有一个1和0的n列表.110000110101110 ..目标是提取包含尽可能多的1的最长子序列.这里例如它是"110000110101"或"100001101011"或"0000110101110"

我对O(n ^ 2)有一个想法,只是从开始到结束扫描所有可能性,但显然有一种方法可以在O(n)中完成.有任何想法吗？

非常感谢!

Answer 1

考虑'10110':

1. 创建一个变量S.创建数组A=[0].

2. 从第一号迭代,并添加1至S如果您发现1选自S减1,如果你发现0和追加S到A.

   • 对于我们的示例序列A将是:[0, 1, 0, 1, 2, 1].A是一个数组,它存储索引前面的1和0之间的差异.序列必须在1和0之间具有相同差异的地方开始和结束.所以现在我们的任务是找到相同数字之间的最长距离A.

3. 现在创建2个空字典(哈希映射)First和Last.

4. 在字典中迭代A并保存每个数字的第一次出现的位置.AFirst

5. 迭代A(从结尾开始)并将每个数字的最后一次出现的位置保存A在字典中Last.

   • 因此,对于我们的示例数组,First将是{0:0, 1:1, 2:4}Last和Last{0:2, 1:5, 2:4}

6. 现在找到key(max_key),其中First和中相应值之间的差异Last是最大的.这个最大差异是子序列的长度.子序列从开始到First[max_key]结束Last[max_key].

我知道它有点难以理解,但它有复杂性O(n) - 四个循环,每个都有复杂度N.你可以用数组替换字典,但它比使用字典更复杂.

Python解决方案.

def find_subsequence(seq):
    S = 0
    A = [0]
    for e in seq:
        if e=='1':
            S+=1
        else:
            S-=1
        A.append(S)
    First = {}
    Last = {}
    for pos, e in enumerate(A):
        if e not in First:
            First[e] = pos
    for pos, e in enumerate(reversed(A)):
        if e not in Last:
            Last[e] = len(seq) - pos
    max_difference = 0
    max_key = None
    for key in First:
        difference = Last[key] - First[key]
        if difference>max_difference:
            max_difference = difference
            max_key  = key
    if max_key is None:
        return ''
    return seq[First[max_key]:Last[max_key]]

find_sequene('10110') # Gives '0110'
find_sequence('1') # gives ''

JF Sebastian的代码更加优化.

额外

此问题与最大子阵列问题有关.它的解决方案也是基于从开始的总结元素:

def max_subarray(arr):
    max_diff = total = min_total = start = tstart = end = 0
    for pos, val in enumerate(arr, 1):
        total += val
        if min_total > total:
            min_total = total
            tstart =  pos
        if total - min_total > max_diff:
            max_diff = total - min_total
            end = pos
            start = tstart
    return max_diff, arr[start:end]