Overview

Given a sequence of numbers, find the maximum sum among all contiguous subsequences whose sum is at least \(0\). An empty subsequence can also be chosen, and its sum is defined as \(0\).

Analysis

This problem is a variant of the well-known “Maximum Subarray Problem.” In the standard maximum subarray problem, we find the maximum sum of a contiguous subsequence, but in this problem there is the restriction that “the sum must not be negative.” However, this restriction can actually be handled naturally by the algorithm — the key idea is to reset the subsequence selection whenever the sum becomes negative.

A naive approach would be to try all combinations of \(l\) and \(r\), but this takes \(O(N^2)\) time, which is impractical since \(N\) can be up to \(2 \times 10^5\) (it would result in TLE). Therefore, we need to consider an algorithm that runs in linear time.

The key insight is to not fix the left endpoint, but instead scan from left to right while maintaining the current running sum. If the sum becomes negative at any point, we can safely discard the previous subsequence (i.e., reset it). This way, we can efficiently maintain “the optimal subsequence ending at the current position” at all times.

Algorithm

A well-known algorithm called Kadane’s Algorithm can be applied to this problem.

The flow of the algorithm is as follows: 1. current_sum: the sum of the current contiguous subsequence (managed so that it never becomes negative) 2. max_sum: the maximum sum seen so far (initialized to \(0\))

Scan the array from left to right and perform the following: - Add the current element to current_sum - If current_sum becomes negative, reset it to current_sum = 0 (i.e., start a new subsequence from here) - Update max_sum with the maximum value of current_sum

By doing this, we can find the maximum sum in linear time.

Example

For the sequence \([-2, 1, -3, 4, -1, 2, 1, -5, 4]\):

i	A[i]	current_sum	max_sum
0	-2	0	0
1	1	1	1
2	-3	0	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

The final answer is \(6\).

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• current_sum is managed so that it never becomes negative (reset to \(0\) if it does)

• max_sum is initialized to \(0\) (since choosing an empty subsequence is allowed)

• Since each element is processed only once, the algorithm runs very efficiently

  Source Code

N = int(input())
A = list(map(int, input().split()))

max_sum = 0
current_sum = 0

for i in range(N):
    current_sum = max(0, current_sum + A[i])
    max_sum = max(max_sum, current_sum)

print(max_sum)

---

This editorial was generated by qwen3-coder-480b.