Pythonで「有効な」配列の最大パワー値を求めるプログラム

問題の概要

n個の整数からなる配列 nums があるとします。配列内の各値は、その要素の「パワー（power）」を表しています。この配列は、次の条件を満たすとき「有効（valid）」であるとみなされます。

• 配列の長さが2より大きいこと
• 配列の先頭と末尾の値が等しいこと

私たちの課題は、配列から不要な要素を削除して残りの部分がこの条件を満たすようにし、その結果得られる配列のパワー値（全要素の合計）の最大値を返すことです。

例として、入力が nums = [3, 4, 5, 3, 4] の場合を考えてみましょう。このとき出力は 16 になります。

配列の先頭にある 3 を削除すると、配列は [4, 5, 3, 4] となり、これは有効な配列です。このときのパワーの合計は 4 + 5 + 3 + 4 = 16 であり、これが与えられた入力から作れる有効な配列の中で最大の合計値です。

解法のアプローチ

有効な配列では両端の値が必ず等しくなるため、「どの値を両端にするか」という視点で各値の出現位置に注目します。ある値の最初の出現位置と最後の出現位置を両端として選べば、その間の要素は自由に削除できます。つまり、区間内の負の値をすべて取り除けば、その区間で達成できる合計は最大になります。

この考え方をもとに、次の手順で問題を解きます。

1. table：空の辞書を用意し、各値について「最初の出現インデックス」と「最後の出現インデックス」を記録します。
2. prefix：値 0 で初期化したリストを用意し、累積和を格納します。
3. negative：値 0 で初期化したリストを用意し、負の値のみの累積和を格納します。
4. nums の各インデックス i と値 j に対して次を処理します。
   ・j が table に存在しない場合：table[j] = [i, 0] を設定
   ・存在する場合：table[j][-1] = i で最後の出現位置を更新
   ・prefix の末尾に「直前の累積和 + j」を追加
   ・negative の末尾に直前の値をコピーして追加し、j < 0 なら negative[-1] += j
5. ans を負の無限大で初期化します。
6. table 内のすべてのペア (i, j) に対して、j が 0 でない場合（同じ値が2回以上出現している場合）次を計算します。
   ・sm1 = prefix[j+1] - prefix[i]：区間全体の合計
   ・j > i+1 の場合：sm2 = negative[j] - negative[i+1]（区間内部の負の値の合計）、それ以外は sm2 = 0
   ・ans = max(ans, sm1 - sm2)
7. ans を返します。

実装例

理解を深めるために、実際のPythonコードを見てみましょう。

def solve(nums):
   table = {}
   prefix = [0]
   negative = [0]
   for i, j in enumerate(nums):
      if j not in table:
         table[j] = [i, 0]
      else:
         table[j][-1] = i
      prefix += prefix[-1] + j,
      negative += negative[-1],
      if j < 0:
         negative[-1] += j

   ans = float('-inf')
   for i,j in table.values():
      if j != 0:
         sm1 = prefix[j+1] - prefix[i]
         sm2 = negative[j] - negative[i+1] if j > i+1 else 0
         ans = max(ans, sm1 - sm2)
   return ans

print(solve([3, 4, 5, 3, 4]))

入力

[3, 4, 5, 3, 4]

出力

16

計算量

このアルゴリズムは配列を一度走査するだけでよいため、時間計算量は O(n) です。また、使用する補助データ構造（辞書・累積和リスト）のサイズも要素数に比例するため、空間計算量も O(n) となります。