如何有效地找到10個最大的子陣列？

Question

我需要找到在陣列10級最大的子陣列（最大長度）與條件arr[high] - arr[low] < delta。現在需要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項目，這就是答案

EDITED

感謝@ 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)用於使用優先級隊列的一般情況。