题目描述

给定一个整数数组$nums$，要求你从数组中找出两个不重叠的子数组，使得这两个子数组的元素和最大。注意，两个子数组的下标必须不重叠。

具体要求如下：

1. 子数组的定义是数组的连续部分。
2. 两个子数组的选择必须满足它们间隔至少一个元素。

输入格式

• 第一行输入一个整数 $n$ ($1 ≤ n ≤ 1000$)，表示数组的长度。
• 第二行输入 $n$ 个整数，表示数组 $nums$ 的元素，元素值范围为 ($-10000 ≤ nums[i] ≤ 10000$)。

输出格式

• 输出两个不重叠子数组和的最大值。

数据范围

• $1 ≤ n ≤ 1000$
• $-10000 ≤ nums[i] ≤ 10000$

示例

输入示例

6
1 -2 3 4 -1 2

输出示例

9