注: これは実際には機能しませんが、いくつかのアイデアが得られるかもしれません。
次のように考えてください。
- を数値
Xの配列とします。
- サブ
sシーケンスの開始のインデックスとします。
- サブ
eシーケンスの終わりのインデックスとします。
任意のパーティション index を選択するとp、最長のサブシーケンスがこのパーティションを横切るか、そのパーティションの左または右に落ちます。最長のサブシーケンスがこのパーティションにまたがる場合、s < p <= e. を見つけるには、X[s] より大きいとsの間の数が最も多いインデックスを見つけます。'e' を見つけるには、X[e] より小さいとの間の数が最も多いインデックスを見つけます。sppe
左側と右側を再帰的にチェックして、より長いサブシーケンスを見つけることができるかどうかを確認できます。
X値で並べ替えられたインデックスがある場合、どのインデックスが右側に最も大きいか、または左側に最も小さいかを見つけることは、線形時間で実行できます。
開始インデックスを見つけるには、並べ替えられたインデックス リストの最初のインデックスから始めて、それが今のところ最高であると言います。次のインデックスがこれまでの最高のインデックスよりも大きい場合、新しい最高のインデックスになるには、現在の最高のインデックスよりもさらに左側にある必要があるため、最高のインデックスから 1 を引きます (ただし、最高のインデックスが何であるかを覚えておいてください)。本当にあった）。次のインデックスが最適なインデックスの左側にある場合は、それを最適なインデックスにします。インデックスごとに、このプロセスを順番に繰り返します。
同様の手順を実行して、右側の終わりに最適なインデックスを見つけることができます。
残っている唯一のトリックは、作業中の範囲のインデックスの並べ替えられたリストを維持することです。これは、最初に数値のセット全体をソートし、それらのインデックスを見つけることで実行できます。次に、再帰の各レベルで、ソートされたインデックスを線形時間で 2 つのサブリストに分割できます。
アイデアの python 実装は次のとおりです。
# Find the index from the given indices that has the most numbers to the
# right of it which are greater in value. The indices are sorted by
# the value of the numbers at that index. We don't even need to know
# what the numbers are.
def longestLowerSequence(indices):
best_index=indices[0]
target_index=best_index
for i in range(0,len(indices)):
if indices[i]<target_index:
best_index=indices[i]
target_index=best_index
else:
target_index-=1
return best_index
# Find the index from the given indices that has the most numbers to the
# left of it which are less in value.
def longestUpperSequence(indices):
n=len(indices)
best_index=indices[n-1]
target_index=best_index
for i in range(0,n):
if indices[n-1-i]>target_index:
best_index=indices[n-1-i]
target_index=best_index
else:
target_index+=1
return best_index
# Return the pair of indices which has the most values between it.
def longestRangeFromSortedIndices(numbers,indices,begin,end):
assert end>begin
if end-begin<=2:
return (indices[begin],indices[end-1])
assert type(indices) is list
partition=(begin+end)/2
left_indices=filter(lambda index: index<partition,indices)
right_indices=filter(lambda index: index>=partition,indices)
assert len(left_indices)>0
assert len(right_indices)>0
left=longestLowerSequence(left_indices)
right=longestUpperSequence(right_indices)
left_range=longestRangeFromSortedIndices(numbers,indices,begin,partition)
right_range=longestRangeFromSortedIndices(numbers,indices,partition,end)
best_size=countBetween(numbers,left,right)
best_range=(left,right)
left_size=countBetween(numbers,left_range[0],left_range[1])
right_size=countBetween(numbers,right_range[0],right_range[1])
if left_size>best_size:
best_size=left_size
best_range=left_range
if right_size>best_size:
best_size=right_size
best_range=right_range
return best_range
def sortedIndices(numbers):
return sorted(range(len(numbers)),key=lambda i: numbers[i])
def longestInterval(numbers):
indices=sortedIndices(numbers)
longest_range=longestRangeFromSortedIndices(numbers,indices,0,len(numbers))
return (numbers[longest_range[0]],numbers[longest_range[1]])