解题思路

给定长度为 n 的整数序列，需选择两个不相交且间隔元素数 ≥ K 的非空连续子段，使两段元素和最大。 核心做法是两遍 Kadane（最大子段和）+ 一次线性合并：

1. 从左到右求：

   • endMax[i]：以位置 i 结尾的最大子段和（Kadane 转移 endMax[i]=max(a[i], endMax[i-1]+a[i])）。
   • leftBest[i]：在区间 [1..i] 内任意子段的最大和（即 leftBest[i]=max(leftBest[i-1], endMax[i])）。

2. 从右到左求：

   • startMax[i]：以位置 i 开始的最大子段和（startMax[i]=max(a[i], startMax[i+1]+a[i])）。
   • rightBest[i]：在区间 [i..n] 内任意子段的最大和（rightBest[i]=max(rightBest[i+1], startMax[i])）。

3. 合并答案：设左段完全落在 [..i]，右段完全落在 [i+K+1..]，则候选值为 leftBest[i] + rightBest[i+K+1]。 枚举 i = 1..(n-K-1)（1-based；实现用 0-based 即 i=0..n-K-2）取最大即可。

该方法保证两段之间至少隔开 K 个元素；允许选取长度为 1 的子段，能正确处理全为负数的情况。

复杂度分析

• 时间复杂度：两次线性 DP + 一次线性合并，整体 O(n)（每组数据）。
• 空间复杂度：使用若干长度为 n 的数组，O(n)。若需可通过滚动变量把 endMax/startMax 压到 O(1)。

代码实现

Python

import sys

# 功能函数：返回一组数据的答案
def solve_case(n, K, a):
    # 左侧：以 i 结尾的最大和 & 前缀内任意子段最大和
    endMax = [0] * n
    leftBest = [0] * n
    endMax[0] = a[0]
    leftBest[0] = a[0]
    for i in range(1, n):
        endMax[i] = max(a[i], endMax[i - 1] + a[i])   # Kadane
        leftBest[i] = max(leftBest[i - 1], endMax[i]) # 前缀最优

    # 右侧：以 i 开始的最大和 & 后缀内任意子段最大和
    startMax = [0] * n
    rightBest = [0] * n
    startMax[n - 1] = a[n - 1]
    rightBest[n - 1] = a[n - 1]
    for i in range(n - 2, -1, -1):
        startMax[i] = max(a[i], startMax[i + 1] + a[i])
        rightBest[i] = max(rightBest[i + 1], startMax[i])

    # 合并：左段在 [..i]，右段在 [i+K+1..]
    INF_NEG = -10**18
    ans = INF_NEG
    limit = n - K - 1  # i 最大到 n-K-2（0-based）
    for i in range(0, limit):
        ans = max(ans, leftBest[i] + rightBest[i + K + 1])
    return ans

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1
    out = []
    for _ in range(t):
        n = int(data[idx]); idx += 1
        K = int(data[idx]); idx += 1
        a = list(map(int, data[idx:idx + n])); idx += n
        out.append(str(solve_case(n, K, a)))
    print("\n".join(out))

if __name__ == "__main__":
    main()

Java

// 注意：类名必须为 Main
import java.io.*;
import java.util.*;

public class Main {
    // 功能函数：返回一组数据的答案
    static long solveCase(int n, int K, long[] a) {
        long[] endMax = new long[n];    // 以 i 结尾的最大和
        long[] leftBest = new long[n];  // [0..i] 内最佳
        endMax[0] = a[0];
        leftBest[0] = a[0];
        for (int i = 1; i < n; i++) {
            endMax[i] = Math.max(a[i], endMax[i - 1] + a[i]);
            leftBest[i] = Math.max(leftBest[i - 1], endMax[i]);
        }

        long[] startMax = new long[n];   // 以 i 开始的最大和
        long[] rightBest = new long[n];  // [i..n-1] 内最佳
        startMax[n - 1] = a[n - 1];
        rightBest[n - 1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            startMax[i] = Math.max(a[i], startMax[i + 1] + a[i]);
            rightBest[i] = Math.max(rightBest[i + 1], startMax[i]);
        }

        long ans = Long.MIN_VALUE / 4;
        int limit = n - K - 1; // i in [0, n-K-2]
        for (int i = 0; i < limit; i++) {
            ans = Math.max(ans, leftBest[i] + rightBest[i + K + 1]);
        }
        return ans;
    }

    public static void main(String[] args) {
        // 简洁输入：Scanner 足够覆盖此数据范围
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int T = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int n = sc.nextInt();
            int K = sc.nextInt();
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = sc.nextLong();
            sb.append(solveCase(n, K, a)).append('\n');
        }
        System.out.print(sb.toString());
        sc.close();
    }
}

C++

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

// 功能函数：返回一组数据的答案
long long solve_case(int n, int K, const vector<long long>& a) {
    vector<long long> endMax(n), leftBest(n);
    endMax[0] = a[0];
    leftBest[0] = a[0];
    for (int i = 1; i < n; ++i) {
        endMax[i] = max(a[i], endMax[i - 1] + a[i]);       // Kadane 以 i 结尾
        leftBest[i] = max(leftBest[i - 1], endMax[i]);     // 前缀最佳
    }

    vector<long long> startMax(n), rightBest(n);
    startMax[n - 1] = a[n - 1];
    rightBest[n - 1] = a[n - 1];
    for (int i = n - 2; i >= 0; --i) {
        startMax[i] = max(a[i], startMax[i + 1] + a[i]);   // Kadane 以 i 开始
        rightBest[i] = max(rightBest[i + 1], startMax[i]); // 后缀最佳
    }

    long long ans = LLONG_MIN / 4;
    int limit = n - K - 1; // i in [0, n-K-2]
    for (int i = 0; i < limit; ++i) {
        ans = max(ans, leftBest[i] + rightBest[i + K + 1]);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    if (!(cin >> T)) return 0;
    while (T--) {
        int n, K;
        cin >> n >> K;
        vector<long long> a(n);
        for (int i = 0; i < n; ++i) cin >> a[i];
        cout << solve_case(n, K, a) << "\n";
    }
    return 0;
}

本题为2024年10月15日百度机考原题

百度机考的介绍点击这里

题目内容

输入一个长度为$n$的整数序列$a_1,a_2,...a_n$。你的任务是恰好选择两个非空子段。子段是指原序列中的连续一段。这两个子段不能有重复部分，且他们之间相隔必须大于$K$。例如，选择子段[$1,5$]和[$8,10$]在$K=2$时合法，但是在$K≥3$时就不合法了。

你需要最大化你选择的这两个子段内的整数之和。请求出这个最大值。

输入描述

第一行输入一个正整数$T$，表示数据组数。

对于每一组数据，第一行输入两个整数$n,K$。第二行输入$n$个整数$a_1,a_2,...a_n$。

$1≤n≤10^5,-10^4≤a_i≤10^4,0≤k≤n-2,1≤T≤5$

输出描述

对于每一组数据，输出一行一个整数，表示答案。

样例1

输入

3
5 3
-1 1 2 3 -1
8 3
5 5 -1 -2 3 -1 2 -2
6 0
5 -1 5 0 -1 9

输出

-2
12
18

说明

第一组数据,只能选择[$1,1$]和[$5,5$]，这样答案就是$-2$。

第二组数据，可以选择[$1,2$]和[$7,7$]，这样答案就是$5+5+2=12$。

第三组数据,可以选择[$1,4$]和[$6,6$]，这样答案就是$5+(-1)+5+0+9=18$。