0

私がしばらくの間解決しようとしてきたこの問題を誰かが助けてくれますか?

数値の配列 A[1,2...n] があり、Divide an Conquer メソッドを使用して、連続して増加する最長のサブ シーケンスを見つけたいとします。具体的には、i<=j および A[i]<=A[i+1]<=.....A[j] となるようなインデックス i,j を見つけたいと考えています。たとえば、配列に 4,1,3,5,6,7,5,8,2 がある場合、[1,3,5,6,7] を返す必要があります。

私はこの問題について多くのことを検索しましたが、私が見つけることができるのは、連続した要素のない動的アプローチと最長増加サブシーケンスだけです。

4

2 に答える 2

1

分割統治法は、配列を A 1と A 2のように 2 つに分割することで実現できます。次に、2 つのサブ配列の問題を再帰的に解決したら、元の配列に対する最適解が存在する可能性があるシナリオを検討する必要があります。

オプション 1:最長連続増加サブシーケンスは完全に A 1にあります。この場合、最大長、関連する答え、または返す予定のものはすべて見つかりました。

オプション 2:同様に、最も長く連続して増加するサブシーケンスは完全に A 2にあります。

オプション 3:最も長く連続して増加するサブシーケンスは、部分的に A 1にあり、部分的に配列2にあります。この場合、A 1が配列の左側部分であり、A 2が右側部分であると考えると、基本的には交点から、減少しなくなるまで、または A 1の左端に到達するまで左に移動する必要があります。そして、それが増加しなくなるか、右端に達するまで、A 2を右に進みます。

これらのオプションの中で、最も長いものを選択して完了です。

ただし、分割統治はO(nlogn)時間の複雑さがあるため、この問題の最適な解決策ではないことに注意してください。Jon Bentley の有名な著書Programming Pearlsで言及されているように、彼が最大和連続部分列問題と呼んでいる解は、線形時間計算量を持つことが知られています。そのソリューションは、最大合計ではなく、増加するサブシーケンスを処理するように簡単に適応できます。

このアルゴリズムは、Bentley がスキャンと呼ぶアプローチに基づいており、サブシーケンスはある時点で終了する必要があるという考えに基づいています。

このアプローチは非常にシンプルで、Python の実装を以下に示します。

def maxIncreasing(arr):
    maxLength = 1
    maxStart = 0
    curStart = 0
    curLength = 1
    for i in range(1, len(arr)):
        if arr[i] <= arr[i-1]:
            if curLength > maxLength:
                maxLength = curLength
                maxStart = curStart
            curStart = i
            curLength = 1
        else:
            curLength += 1
    if curLength > maxLength:
        maxLength = curLength
        maxStart = curStart
    return (maxLength, maxStart)
于 2016-03-14T09:08:03.750 に答える