问题化简

我们可以将问题化简为：选中两个下标$i,j$ 使得 $j - i > K$ 。然后在前缀$[1 , i]$ 和 后缀$[j,n]$ 内分别寻找两个子段使得和最大。

前缀/后缀中的最大子段和

现在我们需要在前缀$[1 , i]$ 中寻找最大子段和。那么根据【动态规划4】最大子段和 我们直接求解，答案为$max\{dp_1,dp_2,...,dp_i\}$

又由于这个下标 $i$ 是频繁变化的，所以我们需要对每个不同的 $i$ 都求解一遍答案。那么根据上节课所学的知识，我们可以预处理出$dp$数组的前缀最大值数组。

由于前缀和后缀为对称问题，后缀中的最大子段和也是同样的求解方法。

枚举答案

我们已经预处理出 前缀 和 后缀 的 $dp$ 最大值数组了，假设为$pre$数组 和 $suf$数组 , 那么就考虑如何枚举$i,j$。

首先，双重循环枚举$i,j$是不现实的，复杂度过高。我们考虑从左往右枚举$i$ , 对于确定的$i$ , 我们一定是希望这个$j$ 离$i$ 尽量近，也就是让$j$尽量靠左。这样才能让后缀有尽可能多的位置去考虑。所以我们直接让$j = i + K + 1$ ， 这是离$i$最近的位置。

选择好$i,j$ 之后，答案就是$pre_i + suf_j$ 中的最大值。

python代码

# 读取测试用例数量
t = int(input())
results = []

# 处理每个测试用例
for _ in range(t):
    # 读取每个测试用例的n和k
    n, k = map(int, input().split())

    # 读取数组a
    a = list(map(int, input().split()))

    # 初始化必要的变量
    MIN_VALUE = float('-inf')  
    dp = [MIN_VALUE] * (n + 2)
    pre = [MIN_VALUE] * (n + 2)
    udp = [MIN_VALUE] * (n + 2)
    suf = [MIN_VALUE] * (n + 2)

    # 计算最大子段和（前缀）
    for i in range(1, n + 1):
        dp[i] = max(a[i - 1], dp[i - 1] + a[i - 1])

    # 计算最大子段和的前缀最大值
    for i in range(1, n + 1):
        pre[i] = max(dp[i], pre[i - 1])

    # 计算最大字段和(后缀)
    for i in range(n, 0, -1):
        udp[i] = max(a[i - 1], udp[i + 1] + a[i - 1])

    # 计算最大字段和（后缀部分）
    for i in range(n, 0, -1):
        suf[i] = max(suf[i + 1], udp[i])

    # 计算最终结果
    res = MIN_VALUE
    for i in range(1, n - k + 1):
        res = max(res, pre[i] + suf[i + k + 1])

    results.append(res)

# 输出所有结果
print('\n'.join(map(str, results)))

c++代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    int t;
    cin >> t;  // 读取测试用例数量
    vector<long long> results;  // 使用 long long 存储结果

    while (t--) {
        int n, k;
        cin >> n >> k;  // 读取每个测试用例的n和k
        
        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];  // 读取数组a
        }

        // 初始化必要的变量
        const long long MIN_VALUE = 0-1e18;
        vector<long long> dp(n + 2, MIN_VALUE);   // 用于存储最大子段和的数组
        vector<long long> pre(n + 2, MIN_VALUE);  // 前缀最大值
        vector<long long> udp(n + 2, MIN_VALUE);  // 后缀最大值
        vector<long long> suf(n + 2, MIN_VALUE);  // 存储最大后缀值

        // 计算最大子段和（前缀）
        for (int i = 1; i <= n; ++i) {
            dp[i] = max((long long)a[i - 1], dp[i - 1] + a[i - 1]);
        }

        // 计算最大子段和的前缀最大值
        for (int i = 1; i <= n; ++i) {
            pre[i] = max(dp[i], pre[i - 1]);
        }

        // 计算最大子段和（后缀）
        for (int i = n; i >= 1; --i) {
            udp[i] = max((long long)a[i - 1], udp[i + 1] + a[i - 1]);
        }

        // 计算最大子段和（后缀部分）
        for (int i = n; i >= 1; --i) {
            suf[i] = max(suf[i + 1], udp[i]);
        }

        // 计算最终结果
        long long res = MIN_VALUE;
        for (int i = 1; i <= n - k; ++i) {
            res = max(res, pre[i] + suf[i + k + 1]);
        }

        results.push_back(res);  // 将结果保存
    }

    // 输出所有结果
    for (long long result : results) {
        cout << result << endl;
    }

    return 0;
}

java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();  // 读取测试用例数量
        List<Long> results = new ArrayList<>();  // 使用 long 存储结果

        while (t-- > 0) {
            int n = sc.nextInt();
            int k = sc.nextInt();  // 读取每个测试用例的n和k

            int[] a = new int[n];
            for (int i = 0; i < n; ++i) {
                a[i] = sc.nextInt();  // 读取数组a
            }

            // 初始化必要的变量
            final long MIN_VALUE = -10000;  // 使用 Long.MIN_VALUE 作为最小值
            long[] dp = new long[n + 2];
            Arrays.fill(dp, MIN_VALUE);  // 初始化 dp 数组
            long[] pre = new long[n + 2];
            Arrays.fill(pre, MIN_VALUE);  // 初始化 pre 数组
            long[] udp = new long[n + 2];
            Arrays.fill(udp, MIN_VALUE);  // 初始化 udp 数组
            long[] suf = new long[n + 2];
            Arrays.fill(suf, MIN_VALUE);  // 初始化 suf 数组

            // 计算最大子段和（前缀）
            for (int i = 1; i <= n; ++i) {
                dp[i] = Math.max(a[i - 1], dp[i - 1] + a[i - 1]);
            }

            // 计算最大子段和的前缀最大值
            for (int i = 1; i <= n; ++i) {
                pre[i] = Math.max(dp[i], pre[i - 1]);
            }

            // 计算最大子段和（后缀）
            for (int i = n; i >= 1; --i) {
                udp[i] = Math.max(a[i - 1], udp[i + 1] + a[i - 1]);
            }

            // 计算最大子段和（后缀部分）
            for (int i = n; i >= 1; --i) {
                suf[i] = Math.max(suf[i + 1], udp[i]);
            }

            // 计算最终结果
            long res = MIN_VALUE;
            for (int i = 1; i <= n - k; ++i) {
                res = Math.max(res, pre[i] + suf[i + k + 1]);
            }

            results.add(res);  // 将结果保存
        }

        // 输出所有结果
        for (long result : results) {
            System.out.println(result);
        }

        sc.close();
    }
}

题目内容

输入一个长度为$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$。