0

ブロックはオーバーラップできません。また、隣接することもできません。A の長さが > 2 であると仮定します。

これは、最大サブアレイの合計を見つけるのと非常によく似ており、線形時間で実行できることを知っています。

また、アルゴリズムが最大部分配列の問題を見つけるのと同じように開始されることも確信しています。

これは数日前に聞いた問題で、解決方法を知りたいと思っています。

4

2 に答える 2

2

max-subarray-algorithm を 2 回実行できます。

アルゴリズム

  1. a[i] の前の max-subarray の合計を意味する関数 L[i] を定義します。O(n) の複雑さで左から右に max-subarray-algorithm を実行できます。
  2. a[i] の後の max-subarray の合計を意味する関数 R[i] を定義します。O(n) の複雑さで右から左に max-subarray-algorithm を実行できます。
  3. 1 から n までスキャンすると、答えは最大の L[i] + R[i+1] になります。このステップは O(n) の複雑さになります。
  4. 簡単な証明: 解は配列内の 1 つの要素から分割されるため、各場所の前後の max-subarray の合計を計算するだけです。

コード

def max_two_sub_array():
    sum = l[0] = ls[0] = 0
    for i = 1 to n:
        sum += a[i]
        if sum < 0: sum = 0
        if l[i - 1] > sum:
            l[i] = l[i - 1]
            ls[i] = ls[i - 1] # endpoint of l[i]
        else
            l[i] = sum
            ls[i] = i

    sum = r[n + 1] = 0
    rs[n + 1] = n + 1
    for i = n to 1:
        sum += a[i]
        if r[i + 1] > sum:
            r[i] = r[i + 1]
            rs[i] = rs[i + 1] # startpoint of r[i]
        else
            r[i] = sum
            rs[i] = i
    ans = 0
    for i = 0 to n:
        ans = max(ans, l[i] + r[i + 1])
    return ans
于 2013-01-25T03:11:50.840 に答える
-1

2 ステップ:

  1. O(n) を使用して、配列全体の最大合計のブロックを見つけます。ブロックが a[i] から始まり、a[j] で終わり、合計が S1 であるとします。

  2. O(n) を使用して、前のブロックの合計が最小のブロックを見つけます。合計を S2 とします。

最終的な答えは S1-S2

いくつかの境界ケースを考慮する必要があります。

配列が 1,2,3,2,1 の場合。ステップ1は配列全体をブロックとして返します。ステップ 2 は 1 を返しますが、これは 2 つのブロックが隣接してはならないという要求に違反しています。したがって、ステップ 2 では、a[i+1] から始まり a[j-1] で終わるアルゴリズムを適用する必要があります。

于 2013-01-25T02:17:16.417 に答える