思路解析

目标：在数组中找两个不重叠的子数组，使它们的和之和最大。

核心做法是把问题拆成“左边一个子数组 + 右边一个子数组”，枚举左右的“分割点”。

具体步骤（dp + 预处理）：

1. dp[i]：以 i 结尾 的最大子数组和

题目描述

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

输入格式

• 第一行输入一个整数 $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