Overview

This is a problem where we select a contiguous subarray from a sequence and find the maximum sum. Since an empty subarray (sum of \(0\)) is also allowed, the answer is always at least \(0\).

Analysis

Key Observations

• There are \(O(N^2)\) ways to choose a contiguous subarray (combinations of start point \(l\) and end point \(r\))
• Since empty subarrays are allowed, the answer is \(0\) even if all elements are negative

Problems with the Naive Approach

If we try all \((l, r)\) combinations and calculate each sum: - Combinations: \(O(N^2)\) ways - Calculating each sum: \(O(N)\) - Total: \(O(N^3)\)

Even using prefix sums, this becomes \(O(N^2)\), which results in TLE for \(N = 2 \times 10^5\).

The Key to the Solution

By using Kadane’s Algorithm, we can solve this in \(O(N)\).

The core idea of this algorithm is:

Efficiently update “the maximum sum of a contiguous subarray ending at position \(i\)”

Algorithm

How Kadane’s Algorithm Works

Variable meanings: - current_sum: Maximum sum of a contiguous subarray ending at the current position - max_sum: Maximum sum found so far

At each position \(i\), we make the following choice: 1. Add \(A_i\) to the previous subarray: current_sum + A[i] 2. Start fresh from \(A_i\): \(A_i\) (i.e., discard the previous subarray) 3. Choose an empty subarray: \(0\)

This is expressed as current_sum = max(0, current_sum + A[i]).

Concrete Example

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

\(i\)	\(A_i\)	current_sum update	max_sum
0	-2	max(0, 0+(-2)) = 0	0
1	1	max(0, 0+1) = 1	1
2	-3	max(0, 1+(-3)) = 0	1
3	4	max(0, 0+4) = 4	4
4	-1	max(0, 4+(-1)) = 3	4
5	2	max(0, 3+2) = 5	5
6	1	max(0, 5+1) = 6	6
7	-5	max(0, 6+(-5)) = 1	6
8	4	max(0, 1+4) = 5	6

The answer is \(6\) (subarray \([4, -1, 2, 1]\))

Why This Works

• When current_sum is about to become negative, resetting it to \(0\) = restarting from an empty subarray
• Since the past maximum is recorded in max_sum, there’s no problem with resetting
• Since we consider “the maximum sum ending at that position” at every position, we don’t miss the optimal solution

Complexity

• Time complexity: \(O(N)\) (just one pass through the array)
• Space complexity: \(O(N)\) (for storing the input array. \(O(1)\) if only counting variables)

Implementation Notes

• By initializing both max_sum and current_sum to \(0\), we naturally handle the empty subarray (sum of \(0\))

• Be careful of overflow: The maximum can reach \(N \times 10^9 = 2 \times 10^{14}\), but in Python there’s no integer overflow, so it’s safe

  Source Code

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    
    # Kadane's algorithm to find maximum subarray sum
    # We also allow empty subarray (sum = 0)
    
    max_sum = 0  # Empty subarray has 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)

solve()

---

This editorial was generated by claude4.5opus.