損益の合計が最も大きい連続した期間

配列の処理
問題 13
ふつう
目安 31 分

店の日ごとの損益 (赤字の日もある) から、続いた日々の合計が最も大きくなる期間を探す。全部の期間を足し直さず、前から 1 回たどるだけで答える練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 2 秒までです。

問題

ある店の N 日間の、日ごとの損益が与えられます。損益が正の日は黒字、負の日は赤字です。1 日以上続いた期間 (l 日目から r 日目まで、l は r 以下) を 1 つ選び、その期間の損益の合計を考えます。合計が最も大きくなる期間を選んだときの、その合計を出力してください。

期間は必ず 1 日以上を選びます。全部の日が赤字のときも、何も選ばない (合計 0) ことはできず、赤字が最も小さい 1 日を選んだときの合計が答えです。

入力の形式

N
a_1 a_2 ... a_N

1 行目に日数 N、2 行目に N 日の損益 a_i が半角の空白 1 つで区切られて並びます。

出力の形式

合計の最大を 1 行に出力します。

制約

N は 1 以上 200000 以下です
a_i は -1000000000 以上 1000000000 以下の整数です

入力と出力の例

例 1

3 日目から 6 日目までの 4 + (-1) + 2 + 1 で 6 が最大です。

入力

8
-2 1 -3 4 -1 2 1 -5

出力

例 2

全部の日が赤字です。何も選ばない合計 0 は答えになれないので、赤字が最も小さい 2 日目だけを選んだ -1 が答えです。

入力

3
-3 -1 -2

出力

-1

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

前から 1 日ずつ見ていき、current に「今日で終わる期間の合計の最大」を持ちます。今日の損益を a としたとき、current は「current + a」と「a」の大きいほうに替わります。そのたびに、全体の最大 best を current で更新します。best の初めの値を 1 日目の損益にしておくと、全部の日が赤字でも、0 ではなく赤字が最も小さい日の値が答えになります。N 日を 1 回たどるだけなので O(N) です。

Python

import sys

data = sys.stdin.read().split()
n = int(data[0])
profits = list(map(int, data[1:1 + n]))

best = profits[0]
current = profits[0]
for a in profits[1:]:
    current = current + a if current > 0 else a
    if current > best:
        best = current

print(best)

JavaScript

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const n = data[0];
const profits = data.slice(1, 1 + n);

let best = profits[0];
let current = profits[0];
for (let i = 1; i < n; i++) {
  const a = profits[i];
  current = current > 0 ? current + a : a;
  if (current > best) best = current;
}

console.log(String(best));

計算量

時間は O(N) です。始まりの日を決めて、終わりの日を 1 日ずつ延ばしながら合計を足し進める書き方は O(N × N) で、N が 20 万の入力では 200 億回の足し算になり、時間切れになります。始まりと終わりの組ごとに毎回足し直すと O(N × N × N) で、さらに遅くなります。

よくある間違い

全部の日が赤字のときに 0 を出す。最大の初めの値を 0 にすると起きます。1 日目の損益から始めます
合計がいちばん大きい期間を探すのに、黒字の日だけを足してしまう。間に赤字の日を挟んでも、前後の黒字が大きければ続けたほうが合計は大きくなります
合計が大きくなることを考えない。20 万日がどれも 10 億なら合計は 200 兆です。Python と JavaScript の数ならそのまま扱えますが、ほかの言語で 32 ビットの整数を使うとあふれます

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
n = int(data[0])
profits = list(map(int, data[1:1 + n]))

# ここから書く

入力

8
-2 1 -3 4 -1 2 1 -5

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します