どのように効率よく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. (low, high)の長さと対をプライオリティキュー、または順序を維持したデータ構造で押します。
4. 二つのポインタO(N)よりよく達成することができます使用して、EDITED @ M69に

   おかげでトップ10ポップ、またはトップN項目とその答え

です：

1. 反復スルー各要素は小から大に、最初の要素を指すlowとhighの2つのポインタを設定します。

2. A[high] - A[low] >= deltaまでhighポインタを右に移動し、長さと(low, high)のペアを優先キューまたはO(lg N)回の順序を維持したデータ構造内に押します。

   特殊な場合は、サイズ10の配列を使用して最長の10サブアレイを保存してから、O(1)を使用してこの配列を維持することができます。

3. 移動右へlowポインタ、繰り返し手順2

注lowが常により小さいかhighに等しく、両方のポインタが常に右のみに移動することを、それぞれが一度リストを反復します。だから、O(N)であるか、または優先度キューを使用する一般的なケースの場合はO(N lg N)です。