Pythonで部分配列の最大絶対和を求めるプログラム

問題の概要

整数型の配列 nums が与えられたとします。このとき、ある部分配列 [nums_l, nums_l+1, ..., nums_r-1, nums_r] の絶対和は、次のように定義されます。

|nums_l + nums_l+1 + ... + nums_r-1 + nums_r|

つまり、部分配列内の要素をすべて足し合わせた値の絶対値です。ここでの課題は、nums の任意の部分配列（空の部分配列も許容）の中から、絶対和が最大になるものを見つけ、その値を返すことです。

入力例

たとえば、入力が nums = [2, -4, -3, 2, -6] の場合を考えてみましょう。このとき出力は 11 になります。

理由は、部分配列 [2, -4, -3, 2] を選んだとき、その総和は 2 + (-4) + (-3) + 2 = -3 となり、絶対値を取ると |-3| = 3 ではなく…と一見小さく見えますが、実際には符号を含めた合計 |2 + (-4) + (-3) + 2| の計算では、負の方向に大きく振れる組み合わせ（例：[-4, -3] や [-6] など）との比較で、最大の絶対値を持つ部分配列が最適解となります。結果として得られる最大絶対和は 11 です。

解法のアプローチ

この問題は、有名な「最大部分配列和（Kadaneのアルゴリズム）」を応用して解くことができます。ポイントは、正の方向の最大和と負の方向の最小和（絶対値が最大の負の和）の両方を調べる必要があるという点です。

具体的には、以下の手順で処理を行います。

• n := nums の要素数
• ans := 0、temp := 0 で初期化
• 1回目のループ（正方向の最大和を求める）：i を 0 から n-1 まで繰り返す
  • もし temp < 0 なら、temp := 0 にリセット
  • temp := temp + nums[i]
  • ans := max(ans, |temp|)
• temp := 0 にリセット
• 2回目のループ（負方向の最小和＝絶対値最大の負の和を求める）：i を 0 から n-1 まで繰り返す
  • もし temp > 0 なら、temp := 0 にリセット
  • temp := temp + nums[i]
  • ans := max(ans, |temp|)
• ans を返す

1回目のループでは累積和が負になった時点でリセットすることで正方向の最大和を追跡し、2回目のループでは逆に累積和が正になった時点でリセットすることで負方向の最小値（絶対値が最大の負の連続和）を追跡します。両者の絶対値の最大値が答えになります。

実装例

それでは、上記のアルゴリズムを Python で実装してみましょう。

def solve(nums):
   n = len(nums)
   ans = 0
   temp = 0

   # 正方向の最大部分配列和を求める
   for i in range(n):
      if temp < 0:
         temp = 0
      temp = temp + nums[i]
      ans = max(ans, abs(temp))

   # 負方向の最小部分配列和（絶対値最大）を求める
   temp = 0
   for i in range(n):
      if temp > 0:
         temp = 0
      temp = temp + nums[i]
      ans = max(ans, abs(temp))

   return ans

nums = [2, -4, -3, 2, -6]
print(solve(nums))

入力

[2, -4, -3, 2, -6]

出力

11

計算量について

このアルゴリズムは配列を2回走査するだけなので、時間計算量は O(n)、追加のメモリ使用量は O(1) で済みます。非常に効率的な解法であり、大きな入力サイズにも対応できます。

まとめ

部分配列の最大絶対和を求める問題は、Kadaneのアルゴリズムを正方向・負方向の2パターンで実行するだけで解決できます。累積和の符号に応じてリセットを行うシンプルな発想により、線形時間で最適解を導き出せる点が魅力です。競技プログラミングやコーディング面接でも頻出のテクニックなので、ぜひマスターしておきましょう。