思路解析

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

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

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

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

   • 经典 dp：dp[i] = max(dp[i-1], 0) + a[i]。
   • 它保证子数组必须以 i 作为最后一个下标。

2. udp[i]：以 i 开始 的最大子数组和（从右往左做）

   • 反向 dp：udp[i] = max(udp[i+1], 0) + a[i]。
   • 它保证子数组必须以 i 作为第一个下标。

3. suf[i]：区间 [i, n-1] 内的“以某点开始的最大子数组和”的最大值

   • 即 suf[i] = max(udp[i], udp[i+1], ..., udp[n-1])。
   • 用从右往左的前缀（准确说是后缀最大）维护：suf[i] = max(suf[i+1], udp[i])，并设 suf[n] = 0 方便处理边界。

4. 枚举分割点

   • 将左侧子数组强制以 i 结尾、右侧子数组从 i+1 开始的区间里任选最佳起点：

     • 左侧贡献：dp[i]
     • 右侧最佳贡献：suf[i+1]
     • 总和：dp[i] + suf[i+1]

   • 在所有 i 上取最大值。

时间复杂度 O(n)，空间 O(n)。

说明（是否允许空子数组）： 给定代码中 suf[n] = 0 且枚举到 i = n-1，等价于允许右边子数组为空。 如果题意严格要求两个子数组都非空，只需将枚举范围改为 i = 0..n-2（即不允许把右侧留空），或把 suf[n] 设为负无穷并保留 i = 0..n-1 的枚举。

C++ 实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;  // 输入数组长度
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i]; // 输入数组元素

    // dp[i] 表示以 i 结尾的最大子数组和
    vector<long long> dp(n);
    dp[0] = a[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = max(dp[i - 1], 0LL) + a[i];
    }

    // udp[i] 表示从 i 开始的最大子数组和
    vector<long long> udp(n);
    udp[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        udp[i] = max(udp[i + 1], 0LL) + a[i];
    }

    // suf[i] 表示从区间 [i, n-1] 内任意起点的最大子数组和（后缀最大）
    vector<long long> suf(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
        suf[i] = max(suf[i + 1], udp[i]);
    }

    // 枚举分割点 i，左边取 dp[i]，右边取 suf[i+1]
    long long ans = LLONG_MIN;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, dp[i] + suf[i + 1]);
    }

    cout << ans << "\n";
    return 0;
}

Python 实现（精炼版，等价于你给的代码）

import sys

# 读取输入
data = sys.stdin.read().strip().split()
n = int(data[0])
a = list(map(int, data[1:]))

# dp[i] 表示以 i 结尾的最大子数组和
dp = [0] * n
dp[0] = a[0]
for i in range(1, n):
    dp[i] = max(dp[i - 1], 0) + a[i]

# udp[i] 表示从 i 开始的最大子数组和
udp = [0] * n
udp[-1] = a[-1]
for i in range(n - 2, -1, -1):
    udp[i] = max(udp[i + 1], 0) + a[i]

# suf[i] 表示 [i, n-1] 范围内的最大前缀和（即后缀最大子数组和）
suf = [0] * (n + 1)
for i in range(n - 1, -1, -1):
    suf[i] = max(suf[i + 1], udp[i])

# 枚举分割点 i
ans = -10**18
for i in range(n):
    ans = max(ans, dp[i] + suf[i + 1])

print(ans)

强制两段非空：把最后的循环改为 for i in range(n - 1):。

Java 实现

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine().trim()); // 读取数组长度
        String[] parts = br.readLine().trim().split("\\s+");
        long[] a = new long[n];
        for (int i = 0; i < n; i++) a[i] = Long.parseLong(parts[i]);

        // dp[i]：以 i 结尾的最大子数组和
        long[] dp = new long[n];
        dp[0] = a[0];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], 0L) + a[i];
        }

        // udp[i]：从 i 开始的最大子数组和
        long[] udp = new long[n];
        udp[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            udp[i] = Math.max(udp[i + 1], 0L) + a[i];
        }

        // suf[i]：从 [i, n-1] 内选起点的最大子数组和（后缀最大）
        long[] suf = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = Math.max(suf[i + 1], udp[i]);
        }

        // 枚举分割点 i
        long ans = Long.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, dp[i] + suf[i + 1]);
        }

        System.out.println(ans);
    }
}

题目描述

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