Pythonでリストの先頭・末尾からK個の要素を削除したときの最大合計を求めるプログラム

問題概要

数値のリスト nums と整数 k が与えられます。リストに対してちょうど k 回の削除（ポップ）操作を行う必要があり、各操作ではリストの左端または右端のいずれかから要素を取り除くことができます。このとき、削除した要素の合計値が最大になるように求めるのが目標です。

たとえば、入力が nums = [2, 4, 5, 3, 1]、k = 2 の場合、出力は 6 になります。これは、先頭から 2 と 4 を削除することで合計 6 が得られるためです。

解法のアプローチ：スライディングウィンドウ

この問題は「スライディングウィンドウ」の考え方を使うと効率的に解けます。まず、先頭から k 個の要素をすべて取った場合の合計を初期値とします。その後、「左側から取る要素を1つ減らし、右側から取る要素を1つ増やす」操作を繰り返すことで、左から取る個数と右から取る個数のすべての組み合わせを網羅的に調べることができます。各ステップでの合計を記録し、その最大値が答えとなります。

具体的な手順は以下の通りです。

• window := インデックス 0 から k-1 までの要素の合計
• ans := window
• i を 1 から k まで繰り返す：
  • window := window - nums[k - i]（左側の要素を外す）
  • window := window + nums[-i]（右側の要素を加える）
  • ans := ans と window のうち大きい方
• ans を返す

それでは、実際の実装を見てみましょう。

実装例

class Solution:
   def solve(self, nums, k):
      window = sum(nums[:k])
      ans = window
      for i in range(1, k + 1):
         window -= nums[k - i]
         window += nums[-i]
         ans = max(ans, window)
      return ans
ob = Solution()
nums = [2, 4, 5, 3, 1]
k = 2
print(ob.solve(nums, k))

入力

[2, 4, 5, 3, 1], 2

出力

6

計算量について

このアルゴリズムは、ウィンドウの合計を毎回再計算するのではなく、差分だけを更新しているため非常に効率的です。時間計算量は O(k)、空間計算量は O(1)（追加のデータ構造が不要）となり、k が大きくなっても高速に動作します。