Overview

This is a problem of finding the maximum sum of a contiguous subarray within a given sequence of \(N\) integers. It is also possible to select an empty subarray (choosing no elements), in which case the sum is \(0\).

Analysis

Naive Approach

One approach is to try all possible contiguous subarrays. If we denote the starting position of the subarray as \(l\) and the ending position as \(r\), there are \(O(N^2)\) such combinations. Computing the sum for each takes \(O(N)\), resulting in \(O(N^3)\) overall. Even with prefix sums, the time complexity is \(O(N^2)\). Given the constraint \(N \leq 2 \times 10^5\), an \(O(N^2)\) solution will not run within the time limit (typically around 2 seconds). Therefore, a more efficient \(O(N)\) algorithm is needed.

Hint Toward an Efficient Solution

Consider scanning the sequence from left to right and observing how “the sum of the contiguous subarray ending at the current element” changes. If the cumulative sum up to a certain position becomes negative, rather than carrying over that negative value and adding the next element to it, it is better to cut off at that point and start a fresh sum from the next element (or return to an empty state). This increases the possibility of achieving a larger sum going forward.

This is the idea behind a well-known technique called Kadane’s Algorithm.

Algorithm

Kadane’s Algorithm

The maximum sum can be found by scanning the sequence just once, using the following procedure:

1. Initialize a variable ans to \(0\) to keep track of the maximum sum found so far (accounting for the empty subarray).
2. Initialize a variable current_sum to \(0\) to keep track of the sum of the current contiguous subarray being considered.
3. For each element \(A_i\) in the sequence, repeat the following operations:
   • Add \(A_i\) to current_sum.
   • If current_sum becomes negative, reset current_sum to \(0\).
     • This corresponds to the decision that “rather than carrying over a negative sum, it is better to cut off here and restart from an empty state.”
   • Update ans with max(ans, current_sum).

With this method, by examining each element only once, we can efficiently determine the optimal starting and ending positions.

Complexity

• Time Complexity: \(O(N)\)
  • Since we scan through the elements of the sequence once, the computation completes in time proportional to the number of elements \(N\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the input values as a list.

Implementation Notes

• Fast I/O: Since \(N\) can be as large as \(2 \times 10^5\), in Python we use sys.stdin.read().split() to read all input at once, reducing execution time.

• Initial Value Setting: The problem states that “it is permitted to select no elements, in which case the sum is 0.” By setting the initial value of ans to \(0\), we can correctly output \(0\) even when all elements are negative.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # この方法は、競技プログラミングにおいてPythonで大量の入力を高速に処理する一般的な手法です。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了します。
    if not input_data:
        return
    
    # 最初の要素は数列の長さ N です。
    n = int(input_data[0])
    
    # カデーンのアルゴリズム（Kadane's Algorithm）を用いて、連続部分列の最大和を求めます。
    # 問題文より、空の部分列（和が0）も許容されるため、ans の初期値は 0 とします。
    ans = 0
    current_sum = 0
    
    # 数列の各要素 A_i についてループを回します。
    # インデックス 1 から n までの要素が数列のデータです。
    for i in range(1, n + 1):
        # 現在の値を整数に変換します。
        val = int(input_data[i])
        
        # 現在の連続部分列の合計に val を加算します。
        current_sum += val
        
        # もし合計が負になった場合、それまでの部分列を破棄し、
        # 合計を 0 にリセットします（これは空の部分列を選ぶ、あるいは次の要素から新しく始めることに相当します）。
        if current_sum < 0:
            current_sum = 0
        # これまでの最大合計値（ans）よりも現在の合計（current_sum）が大きい場合、更新します。
        elif current_sum > ans:
            ans = current_sum
            
    # 選考対象（合計が0以上）となる連続部分列の中での最大値を出力します。
    print(ans)

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-preview.