Pythonで昇順部分配列の最大合計を求めるプログラムの書き方

この記事では、正の値のみで構成された配列 nums が与えられたとき、その中に存在する「昇順の部分配列（サブアレイ）」の中で、合計が最大になるものを求める方法を解説します。

問題の定義

部分配列 [nums_l, nums_l+1, ..., nums_r-1, nums_r] が「昇順」であるとは、l <= i < r を満たすすべての i について nums[i] < nums[i+1] が成り立つことを指します。

たとえば、入力が nums = [15, 25, 35, 5, 15, 55] の場合、出力は 75 になります。これは、[5, 15, 55] が合計値最大の昇順部分配列だからです。

アルゴリズムの考え方

この問題は、配列を一度だけ走査する線形時間 O(n) のアルゴリズムで効率的に解けます。手順は以下のとおりです。

• 変数 total と max_total を、どちらも nums[0] で初期化します。
• i を 1 から配列の末尾まで順に処理します。
  • nums[i] > nums[i-1] の場合：現在の昇順が続いているので、total += nums[i] として合計に加算します。
  • それ以外の場合：昇順が途切れたため、total = nums[i] として新しい部分配列の起点とします。
• 各ステップで total > max_total ならば、max_total = total として最大値を更新します。
• 最後に max_total を返します。

Pythonでの実装例

def solve(nums):
    total = nums[0]
    max_total = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            total += nums[i]
        else:
            total = nums[i]
        if total > max_total:
            max_total = total
    return max_total

nums = [15, 25, 35, 5, 15, 55]
print(solve(nums))

入力

[15, 25, 35, 5, 15, 55]

出力

75

処理の流れを追ってみる

上記の例では、まず 15 → 25 → 35 と昇順が続くため total は 75 になります。次に 5 で昇順が崩れるため total は 5 にリセットされ、その後 5 → 15 → 55 で再び 75 となります。結果として最大値 75 が出力されます。

この手法は「カダネのアルゴリズム」の応用であり、計算量は O(n)、追加メモリは O(1) で済むため、大きな配列に対しても高速に動作します。