P2642 Maximum Sum of Two Non-Adjacent Subarrays

Given an integer sequence of length $n$, select two subarrays (contiguous, non-empty segments of the sequence) such that the total sum of the integers in these two subarrays is maximized, and output that total sum. Each subarray must have a minimum length of $1$, and the two subarrays must be separated by at least one element.

The first line contains an integer representing $n$. The second line contains $n$ integers representing the sequence.

Output a single integer, the maximum total sum of the integers in the two selected subarrays.

Constraints: - For $30\%$ of the testdata, $n \le 100$. - For $60\%$ of the testdata, $n \le 10^4$. - For $100\%$ of the testdata, $n \le 10^6$. - All values during the computation are guaranteed to fit within the range of a signed $64$-bit integer. Translated by ChatGPT 5