Overview

This is a problem of finding the maximum sum of a contiguous subarray (interval). However, we do not select intervals with a negative sum, and the empty interval (sum \(0\)) is also allowed.

Analysis

When we want to maximize the sum of a contiguous interval, naively trying all intervals \((l, r)\) gives \(O(N^2)\) intervals. Since \(N \le 2 \times 10^5\), this will certainly result in a time limit exceeded.

The key observation is as follows:

• When we have processed up to a certain position, we only need to know “the maximum sum of a contiguous subarray ending at that position” to process the next element.
• Furthermore, in this problem, since “intervals with negative sum are not selected” and “the empty interval is OK (sum 0)”, if the partial sum becomes negative along the way, it is optimal to discard that interval and restart from 0. This is because if we carry a negative sum forward, no matter what positive values come afterwards, the total will be reduced.

Concrete example: \(A = [3, -5, 4, 2]\) - The first \(3\) is good (sum \(3\)) - Adding \(-5\) gives \(3 + (-5) = -2\), which is negative → Discard this interval, and restart from the “empty interval (0)” - Then adding \(4, 2\) gives \(6\) as the maximum

With this “reset when it becomes negative” approach, we can find the maximum in a single scan.

Algorithm

This is the “empty interval OK” version of Kadane’s algorithm (linear-time maximum subarray sum algorithm).

• cur: the maximum sum of a contiguous subarray ending at the current position with sum \(\ge 0\)
• best: the maximum value seen so far

For each element \(x\), do the following:

1. cur = max(0, cur + x)
   • Add \(x\) to the good interval up to the previous position (cur + x)
   • If it becomes negative, do not adopt that interval and revert to the empty interval (0)
2. best = max(best, cur) to update the maximum

By initializing cur = 0 and best = 0, even if all elements are negative, the answer will be \(0\) from the empty interval (consistent with the problem conditions).

Complexity

• Time complexity: \(O(N)\) (just a single pass through the array)
• Space complexity: \(O(1)\) (no additional arrays used)

Implementation Notes

• The key to this problem is cur = max(0, cur + x), the “cut off at 0” (because the empty interval is allowed).

• \(A_i\) can be up to \(10^9\) and \(N\) is large, so the total can become very large, but Python’s int has arbitrary precision, so there is no need to worry about overflow.

• Since the input is large, we use sys.stdin.buffer.read() for fast input.

  Source Code

import sys

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

    best = 0
    cur = 0
    for x in a:
        cur = max(0, cur + x)
        if cur > best:
            best = cur

    print(best)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.