如何有效地找到10个最大的子阵列？

Question

我需要在条件为arr[high] - arr[low] < delta的数组中找到10个最大的子数组（最大长度）。现在需要50秒（使用Python）。我可以通过修改算法找到最大子数组，用sum < somevalue找到最大子数组。现在，我只是使用for循环并删除每次迭代后找到的最大子数组。我尝试了很多东西，但现在又回到了这个问题上，因为没有什么是正确的。数组已排序。你知道吗

with open(in_file) as f_in, open(out_file, 'w') as f_out:
    dct = {}        
    mainlst = []
    # Read a file and store values in mainlst and map to some strings using dct

    for i in range(10): 
        start = 0
        end = 0
        maxim = 0
        diff = 0
        current = 1
        max_start = 0
        max_end = 0
        while end < len(mainlst)-1:
            end += 1
            diff = mainlst[end] - mainlst[start]                
            current += 1
            while diff > delta:
                start += 1
                diff = mainlst[end] - mainlst[start]
                current -= 1
            if maxim < current:
                maxim = current
                max_start = start
                max_end = end

        print("".join([dct[mainlst[max_start]], ",", str(maxim)]), file=f_out)

        del mainlst[max_start:max_end+1]

编辑：我忘了提另一个条件。子数组不能重叠。你知道吗

Answer 1

有一个O(N lg N)算法：

1. 从小到大遍历每个元素，将当前元素设置为A[low]，O(N)
2. 二元搜索满足不等式A[high]的索引O(lg N)
3. 按O(lg N)次推送优先级队列或任何保持顺序的数据结构中的长度和(low, high)对
4. 弹出前10项或前N项，这就是答案

编辑

由于@m69，使用两个指针可以获得更好的O(N)：

1. 遍历每个元素，从小到大，设置两个指针low和high，最初指向第一个元素

2. 将high指针向右移动直到A[high] - A[low] >= delta，按O(lg N)次推送优先级队列或任何保持顺序的数据结构中的长度和(low, high)对。你知道吗

   对于您的特殊情况，只需使用大小为10的数组来存储最长的10个子数组，然后就可以使用O(1)来维护此数组。

3. 向右移动low指针，重复步骤2。你知道吗

注意low总是小于或等于high，并且两个指针总是只向右移动，每个指针在列表中迭代一次。所以它是O(N)，或者它是O(N lg N)对于使用优先级队列的一般情况。你知道吗