Maximize Sum of Two Non-Overlapping Subarrays

You are given a sequence of N integers. Your task is to determine two non-overlapping contiguous subarrays whose sum is maximized. In other words, you should select two subarrays that do not overlap such that the sum of all their elements is as large as possible.

Formally, let \(S(i, j)\) denote the sum of the subarray starting at index \(i\) and ending at \(j\). You need to find two pairs of indices \((i_1, j_1)\) and \((i_2, j_2)\) with \(0 \leq i_1 \leq j_1 < i_2 \leq j_2 \leq N-1\) that maximize the value \[ \max_{0 \leq j_1 < i_2 \leq N-1} \{S(i_1,j_1) + S(i_2,j_2)\} \]

Note that if the sequence contains less than two elements, it is impossible to form two subarrays, and the answer should therefore be 0.

inputFormat

The input is given via standard input (stdin) with the following format:

1. The first line contains a single integer N, the number of elements in the array.
2. The second line contains N space-separated integers representing the array elements.

outputFormat

Print a single integer to standard output (stdout), which represents the maximum possible sum of two non-overlapping contiguous subarrays.

6
1 2 -1 2 3 -5

8