3

整数の配列 A が与えられます。同じ加重平均を持つ、最大長の 2 つの連続したサブ配列 (両方のサブ配列の長さが等しい必要があります) を見つけたいと考えています。重みは、サブ配列内の位置です。例えば

A=41111921111119
サブアレイ:: (11119) および (11119)

すべてのサブアレイの加重平均を DP で見つけようとしましたが、それらを列ごとに並べ替えて同じ長さの 2 を見つけようとしました。前もって感謝します。

4

2 に答える 2

0

まず、2 つの部分配列の長さは等しくなければならないため、1 から n までの長さを段階的に検討できます。

長さ i については、総複雑度 O(n) ですべてのサブ配列の加重合計を計算できます。次に、合計を並べ替えて、等しいペアがあるかどうかを判断します。

n回ソートすると、スペースはO（n）ですが、時間はO（n ^ 2 log n）になります。

たぶん、質問に記載されている解決策を繰り返しましたか？しかし、これ以上最適化することはできないと思います...

于 2012-09-26T15:25:17.703 に答える
0

最初のステップは、配列をソートすることです。次に、等しい値の任意のペアを識別して、因数分解できます。残りの数字は、次のようにすべて異なります。

2、3、5、9、14、19 ...など

次のステップは、ペアをその中心と比較することです。

2 + 5 == 2 * 3 ?
3 + 9 == 2 * 5 ?
5 + 14 == 2 * 9 ?
9 + 19 == 2 * 14 ?

次のステップは、ネストされたペアを比較することです。つまり、ABCD がある場合は、A+D と B+C を比較します。したがって、上記の例では次のようになります。

2+9 == 3+5 ?
3+15 == 5+9 ?
5+19 == 9+14 ?

次に、トリプルを 2 つの内部値と比較します。

2 + 3 + 9 == 3 * 5 ?
2 + 5 + 9 == 3 * 3 ?
3 + 5 + 14 == 3 * 9 ?
3 + 9 + 14 == 3 * 5 ?
5 + 9 + 19 == 3 * 14 ?
5 + 14 + 19 == 3 * 9 ?

次に、トリプルのペアを比較します。

2 + 3 + 19 == 5 + 9 + 14 ?
2 + 5 + 19 == 3 + 9 + 14 ?
2 + 9 + 19 == 3 + 5 + 14 ?

等々。注文方法は色々あります。1 つの方法は、最初のブラケットを作成することです。たとえば、ABCDEFGH が与えられた場合、最初のブラケットは ABGH 対 CDEF、つまり中心と比較して外側です。次に、比較に従って値を切り替えます。たとえば、ABGH > CDEF の場合、左の値が右の値より大きいすべてのスイッチを試すことができます。この場合、G と H は E と F よりも大きいため、可能な切り替えは次のとおりです。

G <-> E
G <-> F
H <-> E
H <-> F
GH <-> EF

于 2012-09-26T15:01:03.170 に答える