会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
解题思路
我们在长度为 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 个元素后，结束选择的最大和（第二段已结束，后续不再选）
P3696.最大子段和(K=2)
题目描述
给定一个整数数组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
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
