定义$dp[i]$为以$i$结尾的$(1,i)$范围内的最大子段和,定义$udp[i]$为以$i$为起点,$(i,n)$范围内的最大子段和，那么根据题意，全局最大两段不重叠的子段和即为res=max(res,dp[i]+udp[i+k+1])

注意$i+k+1$需小于等于$n$

c++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main()
{
	ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
       int n,k;
       cin>>n>>k;
       vector<int>a(n+1),s(n+1);
       vector<int>dp(n+2),udp(n+2);
       dp[0]=-100000;
       udp[n+1]=-100000;
       for(int i=1;i<=n;i++)cin>>a[i],s[i]=s[i-1]+a[i];
       for(int i=1;i<=n;i++)
       {
        dp[i]=max(a[i],dp[i-1]+a[i]);//计算最大前缀和
       
       }
       for(int i=1;i<=n;i++)
       {
        dp[i]=max(dp[i],dp[i-1]);//计算最大字段和
       }
    
       for(int i=n;i>=1;i--)
       {
        udp[i]=max(a[i],udp[i+1]+a[i]);//计算最大后缀和
       }
       for(int i=n;i>=1;i--)
       {
        udp[i]=max(udp[i+1],udp[i]);//计算最大字段和
       }
       int res=-2e9;
       for(int i=1;i+k+1<=n;i++)
       {
        res=max(res,dp[i]+udp[i+k+1]);
       }
       cout<<res<<endl;
    }
}

python

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    index = 0
    t = int(data[index])
    index += 1
    results = []
    
    for _ in range(t):
        n = int(data[index])
        k = int(data[index + 1])
        index += 2
        
        a = list(map(int, data[index:index + n]))
        index += n
        
        s = [0] * (n + 1)
        dp = [-100000] * (n + 2)
        udp = [-100000] * (n + 2)
        
        for i in range(1, n + 1):
            s[i] = s[i - 1] + a[i - 1]
        
        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):
            dp[i] = max(dp[i], dp[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):
            udp[i] = max(udp[i + 1], udp[i])  # 计算最大字段和

        res = -2e9
        for i in range(1, n - k + 1):
            res = max(res, dp[i] + udp[i + k + 1])

        results.append(res)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        
        while (t-- > 0) {
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            int[] a = new int[n + 1];
            long[] s = new long[n + 1];
            long[] dp = new long[n + 2];
            long[] udp = new long[n + 2];
            Arrays.fill(dp, -100000);
            Arrays.fill(udp, -100000);
            
            for (int i = 1; i <= n; i++) {
                a[i] = scanner.nextInt();
                s[i] = s[i - 1] + a[i];
            }

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

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

            long res = -2000000000;
            for (int i = 1; i + k + 1 <= n; i++) {
                res = Math.max(res, dp[i] + udp[i + k + 1]);
            }
            System.out.println(res);
        }
        scanner.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$。