解题思路

我们在长度为 n 的数组中选择恰好两个互不相交的连续子段，并要求两段之间至少有 1 个未选元素（休息位），目标是两段和的最大值。采用状态机 DP，严格使用 dp[i][1/2/3/4/5] 形式：

• dp[i][1]：处理到第 i 个元素（含）后，仍未选择子段的最大和
• dp[i][2]：处理到第 i 个元素后，处于第一个子段内的最大和（第一个子段正在累加）
• dp[i][3]：处理到第 i 个元素后，处于休息状态的最大和（第一段已结束，当前元素不选，用于保证至少 1 个间隔）
• dp[i][4]：处理到第 i 个元素后，处于第二个子段内的最大和（第二个子段正在累加）
• dp[i][5]：处理到第 i 个元素后，结束选择的最大和（第二段已结束，后续不再选）

题目描述

给定一个整数数组$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

开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写