累積和 という概念を導入します。

長さ \(N\) の数列 \(A=(A_1,A_2,\dots,A_N)\) に対し、数列 \(B=(B_0,B_1,\dots,B_N)\) を以下のように定めます。

• \(B_0=0\)
• \(B_1=A_1\)
• \(B_2=A_1+A_2\)
• \(\dots\)
• \(B_N=A_1+A_2+\dots+A_N\)

この数列こそが先頭からの累積和です。この \(B\) は、 \(B_i = B_{i-1} + A_i\) を \(i\) の昇順に計算していくことで得ることができます。

この \(B\) を利用すると、 \(A_l+A_{l+1}+\dots+A_r\) の値を \(B_r-B_{l-1}\) として計算できます。
なぜなら、 \(B_r-B_{l-1} = (A_1+A_2+\dots+A_r)-(A_1+A_2+\dots+A_{l-1}) = A_l+A_{l+1}+\dots+A_r\) となるからです。

全ての右端 \(r\) について、 \(A_l+A_{l+1}+\dots+A_r\) を最大化するような左端 \(l\) を求めたいです。どうすればよいでしょうか？

\(A_l+A_{l+1}+\dots+A_r\) は \(B_r-B_{l-1}\) で求めることができました。
今回、 \(r\) を固定して考えているため \(B_r\) を変えることはできません。
よって、 \(B_{l-1}\) の部分が最小となるものを選ぶことで \(B_r-B_{l-1}\) を最大化できます。
選択の候補は \(B_0,B_1,\dots,B_r\) です。 \(B_r\) を選んだ場合 \(B_r-B_{l-1}=B_r-B_r=0\) となりますが、これは空の区間に対応します。今回はそのような行為が許されています。
\(B_0,B_1,\dots,B_r\) までの中の最小値は、 \(r\) を増やしていく過程でそれまでの最小値と現在の \(B_r\) とを比較することで保持しておくことができます。

結局、以下の手順で解くことができます。

• 暫定的な答え \(res=0\) 、累積和の最小値 \(low=0\) 、現在の累積和 \(hei=0\) と初期化する。 (余談: \(hei\) は標高(height)のイメージからそう名付けています)
• \(i=1,2,\dots,N\) について、以下を繰り返す。
  • \(hei\) に \(A_i\) を加算する。
    • この時点での \(hei\) は \(A_1\) から \(A_i\) までの累積和 \(B_i\) となります。
  • \(low := \min(low,hei)\) と更新する。
    • この時点での \(low\) は \(B_0,B_1,\dots,B_i\) の中の最小値となります。
  • \(res := \max(res,hei-low)\) と更新する。
    • この時点での \(hei-low\) は、 \(A_i\) が右端となる場合の連続区間の最大和に対応します。

時間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N;
  cin >> N;
  ll res=0,low=0,hei=0;
  for(ll i=0;i<N;i++){
    ll A;
    cin >> A;
    hei+=A;
    low=min(low,hei);
    res=max(res,hei-low);
  }
  cout << res << "\n";
  return 0;
}