解题思路

我们在长度为 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 个元素后，结束选择的最大和（第二段已结束，后续不再选）

设当前数为 x = a[i]（下标从 1 开始），转移为（均从 i-1 推到 i）：

• dp[i][1] = dp[i-1][1] 继续不开始。
• dp[i][2] = max(dp[i-1][2] + x, dp[i-1][1] + x) 继续第一段，或从未开始转入第一段并吸收 x。
• dp[i][3] = max(dp[i-1][3], dp[i-1][2]) 休息：延续休息，或在 i-1 把第一段收尾（当前 i 不选，作为休息位）。
• dp[i][4] = max(dp[i-1][4] + x, dp[i-1][3] + x) 继续第二段，或在休息之后从当前 i 开启第二段（保证两段间至少 1 个未选）。
• dp[i][5] = max(dp[i-1][5], dp[i-1][4]) 结束：延续已结束，或在 i-1 把第二段收尾（当前 i 不选）。

初始化（i=0 表示尚未处理任何元素）：

• dp[0][1] = 0，其余 dp[0][2..5] = -∞ 遍历完后答案为 max(dp[n][4], dp[n][5])（第二段延续到末尾或更早结束）。 该设计保证：必须经历“第一段 → 休息 → 第二段”的路径才能得到有限值，从而满足“两段且至少 1 个休息位”。

复杂度分析

• 时间复杂度：每个位置常数次转移，O(n)。
• 空间复杂度：使用二维 DP（按题意要求 dp[i][1..5]），O(n)。 若需进一步优化，可将其滚动为 O(1) 空间，但本题按要求保留二维形式。

代码实现

Python

# 功能实现放在外部函数；主函数仅负责输入输出
# 输入格式：第一行 n；第二行数组
# 当需要字符串分割时，Python 优先使用 literal_eval，失败再退化为空格分割

import sys
from ast import literal_eval

INF_NEG = -10**18

def max_two_segments_with_rest_dp(arr):
    """二维 DP：dp[i][1..5]，恰好两段，中间至少 1 个休息位"""
    n = len(arr)
    # dp[i][s]：处理到第 i 个（1..n），状态 s 的最大和
    dp = [[INF_NEG]*6 for _ in range(n+1)]
    dp[0][1] = 0  # 初始：未开始

    for i in range(1, n+1):
        x = arr[i-1]
        dp[i][1] = dp[i-1][1]                         # 未开始
        dp[i][2] = max(dp[i-1][2] + x, dp[i-1][1] + x) # 第一段中
        dp[i][3] = max(dp[i-1][3], dp[i-1][2])         # 休息（当前不选）
        dp[i][4] = max(dp[i-1][4] + x, dp[i-1][3] + x) # 第二段中
        dp[i][5] = max(dp[i-1][5], dp[i-1][4])         # 已结束（当前不选）

    return max(dp[n][4], dp[n][5])

def main():
    data = sys.stdin.read().strip().splitlines()
    n = int(data[0].strip())
    # 读取数组，优先尝试 literal_eval
    line = data[1].strip()
    try:
        parsed = literal_eval(line)
        if isinstance(parsed, int):
            arr = [parsed]
        else:
            arr = list(parsed)
    except Exception:
        # 回退为空格分割；若不足 n，则把后续行拼接
        tokens = line.split()
        idx = 2
        while len(tokens) < n and idx < len(data):
            tokens += data[idx].split()
            idx += 1
        arr = list(map(int, tokens[:n]))

    ans = max_two_segments_with_rest_dp(arr)
    print(ans)

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main（ACM 风格）；默认不用快读
// 按要求使用 dp[i][1..5] 的二维 DP
import java.util.*;
import java.util.regex.*;

public class Main {
    static final long NEG = (long)-4e18; // 作为 -∞ 使用

    // 外部函数：二维 DP 求解
    static long solveWithDP(int[] a) {
        int n = a.length;
        long[][] dp = new long[n + 1][6];
        for (int i = 0; i <= n; i++) Arrays.fill(dp[i], NEG);
        dp[0][1] = 0; // 初始状态：未开始

        for (int i = 1; i <= n; i++) {
            int x = a[i - 1];
            dp[i][1] = dp[i - 1][1];                          // 未开始
            dp[i][2] = Math.max(dp[i - 1][2] + x, dp[i - 1][1] + x); // 第一段中
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2]);   // 休息（不选）
            dp[i][4] = Math.max(dp[i - 1][4] + x, dp[i - 1][3] + x); // 第二段中
            dp[i][5] = Math.max(dp[i - 1][5], dp[i - 1][4]);   // 已结束（不选）
        }
        return Math.max(dp[n][4], dp[n][5]);
    }

    public static void main(String[] args) {
        // 输入：第一行 n；后续为数组
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 根据要求：当可能出现类似 "[1, -2, 3]" 的格式时，优先使用“替换字符 + 输入流”的方式解析
        sc.useDelimiter("\\A"); // 读取剩余所有内容
        String rest = sc.hasNext() ? sc.next() : "";
        // 将非数字与非负号的字符替换为空格，然后按空格切分
        String cleaned = rest.replaceAll("[^0-9-]+", " ");
        String[] parts = cleaned.trim().isEmpty() ? new String[0] : cleaned.trim().split("\\s+");

        int[] a = new int[n];
        int idx = 0;
        for (int i = 0; i < n && idx < parts.length; i++) {
            a[i] = Integer.parseInt(parts[idx++]);
        }
        // 若仍不足（极端输入），补个兜底：这在默认合法输入下通常不会触发
        while (idx < n) a[idx] = 0;

        long ans = solveWithDP(a);
        System.out.println(ans);
    }
}

C++

// 按要求：功能实现放外部函数；主函数进行输入输出
// 当数组可能是 "[1, -2, 3]" 一类格式时，采用“替换字符 + 输入流”解析
#include <bits/stdc++.h>
using namespace std;

const long long NEG = (long long)-4e18; // 作为 -∞

long long solveWithDP(const vector<long long>& a) {
    int n = (int)a.size();
    // dp[i][s]：处理到第 i 个（1..n），状态 s 的最大和
    vector<array<long long, 6>> dp(n + 1);
    for (int i = 0; i <= n; ++i) dp[i].fill(NEG);
    dp[0][1] = 0; // 初始：未开始

    for (int i = 1; i <= n; ++i) {
        long long x = a[i - 1];
        dp[i][1] = dp[i - 1][1];                              // 未开始
        dp[i][2] = max(dp[i - 1][2] + x, dp[i - 1][1] + x);   // 第一段中
        dp[i][3] = max(dp[i - 1][3], dp[i - 1][2]);           // 休息（不选）
        dp[i][4] = max(dp[i - 1][4] + x, dp[i - 1][3] + x);   // 第二段中
        dp[i][5] = max(dp[i - 1][5], dp[i - 1][4]);           // 已结束（不选）
    }
    return max(dp[n][4], dp[n][5]); // 第二段到末尾或更早结束
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    // 读取剩余输入到字符串，进行“替换字符 + 输入流”解析
    string dummy;
    getline(cin, dummy); // 吃掉行尾
    string all, line;
    while (getline(cin, line)) {
        all += ' ';
        all += line;
    }
    // 将所有非数字与非负号字符替换为空格
    for (char& c : all) {
        if (!(c == '-' || (c >= '0' && c <= '9'))) c = ' ';
    }
    stringstream ss(all);
    vector<long long> a;
    a.reserve(n);
    long long v;
    while ((int)a.size() < n && (ss >> v)) a.push_back(v);
    // 默认输入合法，若不足则不额外处理

    cout << solveWithDP(a) << "\n";
    return 0;
}

题目描述

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