概要

各日に働くと \(A_i-1\) 円の利益になるので、配列 \(B_i=A_i-1\) の「連続部分和の最大値（最大部分配列和）」を求める問題です。

考察

連続して \(i\) 日目から \(j\) 日目まで働くときの実質収入は
$\((A_i+\cdots+A_j)-(j-i+1)\)\( ですが、これは各日ごとに \)1\( 円引かれているだけなので、 \)\( (A_i-1) + (A_{i+1}-1) + \cdots + (A_j-1) \)$ と同じです。

つまり、\(B_i = A_i - 1\) と置けば、求めたいものは - 配列 \(B\) の連続する区間の和の最大値

になります。

素朴な方法がだめな理由

全ての区間 \((i,j)\) を試して和を計算すると区間数は約 \(N^2/2\) 個あり、
\(N \le 2\times 10^5\) では \(O(N^2)\) は間に合いません（TLE）。

どう解決するか

「今見ている位置で終わる最大の区間和」を1回の走査で更新していくことで、\(O(N)\) で最大部分配列和を求められます（Kadane 法）。

例：\(A=[3,1,2]\) のとき、\(B=[2,0,1]\)
最大の連続部分和は \(2+0+1=3\) なので答えは \(3\)。

アルゴリズム

Kadane 法（動的計画法の一種）を使います。

• \(x = A_i - 1\) を順に見ていく
• cur：i日目で終わる連続区間の最大収入
• best：これまでの最大収入

更新は次の通りです：

• i日目だけで新しく区間を始める：\(x\)
• 直前までの区間にi日目を足す：\(\text{cur}+x\)

よって $\(\text{cur} = \max(x, \text{cur}+x)\)\( \)\(\text{best} = \max(\text{best}, \text{cur})\)$

また「少なくとも1日は働く」必要があるため、空区間（和0）を許す初期化はできません。最初の要素 \(A_1-1\) で cur と best を初期化します。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\)（入力配列を除けば定数）

実装のポイント

• 初期化が重要：必ず1日以上選ぶ必要があるので、best = cur = A[0]-1 とする（0で初期化しない）。

• 各要素は最大で \(10^9\) 程度、\(N\) も大きいので和は \(10^{14}\) くらいになり得ますが、Python の整数なら安全です。

• 入力が大きいので sys.stdin.buffer.read() を使うと高速です。

  ソースコード

import sys

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

    best = cur = a[0] - 1
    for i in range(1, n):
        x = a[i] - 1
        cur = max(x, cur + x)
        best = max(best, cur)

    print(best)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。