\(1 \leq l \leq r \leq N\) を満たす整数の組 \((l, r)\) は \(\Theta(N^2)\) 個あるため、これら全てを愚直に調べる方法では \(\Omega(N^2)\) 時間かかり、実行制限時間に間に合わせることは絶望的です。 そのため、ここでは累積和や累積 \(\min\)を 用いた \(O(N)\) 時間のアルゴリズムを考えます。

\(A\) の累積和配列を \(S\) とし、\(S\) の累積 \(\min\) 配列を \(M\) とします。 つまり、\(S = (S_0, S_1, \ldots, S_N)\) を

\[S_i = \begin{cases} A_1 +A_2 + \cdots + A_i & i = 1, 2, \ldots, N,\\ 0 & i = 0 \end{cases} \]

で定め、 さらに \(M = (M_0, M_1, \ldots, M_N)\) を、 \(i = 0, 1, \ldots, N\) について

\[M_i = \min\lbrace S_0, S_1, \ldots, S_i\rbrace\]

で定めます。

\(S\) と \(M\) はそれぞれ、\(S_i = S_{i-1} + A_i\) および \(M_i = \min\lbrace M_{i-1}, S_i \rbrace\) という関係を用いて、それぞれ \(O(N)\) 時間で計算できます。

このとき、本問題の答えは、

\[ \begin{aligned} \max_{(l, r):1 \leq l \leq r \leq N} (A_l + A_{l+1} + \cdots + A_r) &=\max_{(l, r):1 \leq l \leq r \leq N} (S_r - S_{l-1})\\ &=\max_{1 \leq r \leq N} \max_{l:1 \leq l \leq r}(S_r - S_{l-1})\\ &=\max_{1 \leq r \leq N} (S_r - \min_{l:1 \leq l \leq r} S_{l-1})\\ &=\max_{1 \leq r \leq N} (S_r - M_{r-1})\\ \end{aligned} \]

と表されます。よって、すべての \(r = 1, 2, \ldots, N\) について \(S_r - M_{r-1}\) を計算し、そのうち最大のものを答えとして出力すればよく、これは \(O(N)\) 時間で実現可能です。

よって、本問題を \(O(N)\) 時間で解くことができます。

以下に、C++ 言語による正解例を記載します。

#include <iostream>
using namespace std;
typedef long long ll;

ll n;
ll a[200005], s[200005], m[200005];

int main(void)
{
  cin >> n;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];
  m[0] = s[0];
  for(int i = 1; i <= n; i++) m[i] = min(m[i-1], s[i]);
  
  ll ans = -2e18;
  for(int i = 1; i <= n; i++) ans = max(ans, s[i] - m[i-1]);
  cout << ans << endl;

  return 0;
}