Pythonで最高地点の標高を求めるアルゴリズム：累積和の考え方と実装例

ロードトリップに出かけたバイク乗りを想像してみてください。旅路にはn個の地点があり、それぞれ標高が異なります。バイク乗りは標高0の地点0から旅をスタートします。ここで、n個の要素を持つ配列gainが与えられ、gain[i]は地点iと地点i+1の間の標高の変化量（正の値なら上り、負の値なら下り）を表すものとします。このとき、旅路全体で最も高い地点の標高を求めるのが今回の課題です。

たとえば、入力がgain = [-4, 2, 6, 1, -6]だった場合、出力は5になります。これは、各時点の標高が[0, -4, -2, 4, 5, -1]と推移し、その中で最大値が5であるためです。

解き方のアプローチ

この問題は「累積和（ランニングサム）」の考え方を使うと、非常にシンプルに解くことができます。手順は以下の通りです。

• maximum := 0（これまでの最大標高）
• run_alt := 0（現在の標高）
• gain内の各要素deltaについて以下を繰り返す：
  • run_alt := run_alt + delta（標高を更新）
  • maximum := maximumとrun_altのうち大きい方
• maximumを返す

この方法なら、配列を一度走査するだけで答えが得られるため、計算量はO(n)、追加のメモリはO(1)と非常に効率的です。

Pythonでの実装例

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

def solve(gain):
    maximum = 0
    run_alt = 0

    for delta in gain:
        run_alt += delta
        maximum = max(maximum, run_alt)

    return maximum

gain = [-4, 2, 6, 1, -6]
print(solve(gain))

入力

[-4,2,6,1,-6]

出力

5

まとめ

この問題のポイントは、各地点の標高を順番に足し合わせながら、その都度最大値を更新していく点です。累積和のテクニックは、気温の変化や口座残高の推移など、連続的な増減を扱うさまざまな場面で応用できるため、ぜひ覚えておきましょう。