解题思路

本题是经典的“恰好选 K 段不相交连续子数组使总和最大”的动态规划问题。设：

• dp[k][i]：在前 i 个元素中恰好选 k 段、且最后一段已结束（结束位置 ≤ i）时的最大总和（也可理解为全局最优）。
• end[k][i]：在前 i 个元素中恰好选 k 段、且第 k 段必须以 i 结尾的最大总和（局部最优）。

转移：

• end[k][i] = max(end[k][i-1] + a[i], dp[k-1][i-1] + a[i]) 含义：要让第 k 段以 i 结尾，要么把上一位置 i-1 的“以结尾”为基础继续延长，要么从一个完成了 k-1 段的状态在 i 开新段。
• dp[k][i] = max(dp[k][i-1], end[k][i]) 含义：i 位置的全局最优要么不在 i 结束（沿用 i-1 的全局最优），要么就是以 i 结束（取 end[k][i]）。

初始化：

• dp[0][i] = 0（从前 i 个元素中选 0 段，总和为 0），
• 其余不合法状态置为负无穷。

实现时用“滚动数组”将空间降为 O(N)：

• 维护 dpPrev[i] = dp[k-1][i] 与 dpCurr[i] = dp[k][i]，以及当前层的 end 数组。

该 DP 保证“恰好 K 段”和“段非空且不相交”。

复杂度分析

• 时间复杂度：O(N * K)（两层循环，每个状态 O(1) 转移）
• 空间复杂度：O(N)（滚动数组保存上一层与当前层的 DP 值）

代码实现

Python

# 题意函数放在外部；主函数只负责输入输出
import sys

def max_k_segments(a, N, K):
    NEG = -10**30  # 足够小的负无穷
    # 1-based 方便处理
    a = [0] + a

    # dpPrev[i] 表示 dp[k-1][i]，初始为 k=0 的层：dp[0][i] = 0
    dpPrev = [0] * (N + 1)

    for _ in range(1, K + 1):
        end = [NEG] * (N + 1)     # end[k][i]
        dpCurr = [NEG] * (N + 1)  # dp[k][i]，dpCurr[0] 应为负无穷（无法用 0 个元素选 >=1 段）
        for i in range(1, N + 1):
            # 第 k 段以 i 结尾：要么延长，要么新开
            extend = end[i - 1] + a[i]
            start_new = dpPrev[i - 1] + a[i]
            end[i] = extend if extend > start_new else start_new
            # 全局最优：要么不以 i 结尾，要么以 i 结尾
            dpCurr[i] = dpCurr[i - 1] if dpCurr[i - 1] > end[i] else end[i]
        dpPrev = dpCurr  # 下一层迭代

    return dpPrev[N]

def main():
    data = sys.stdin.read().strip().split()
    N, K = map(int, data[:2])
    arr = list(map(int, data[2:2 + N]))
    ans = max_k_segments(arr, N, K)
    print(ans)

if __name__ == "__main__":
    main()

Java

// 题意函数放在外部；主函数只负责输入输出
import java.io.*;
import java.util.*;

public class Main {
    // 计算恰好K段不相交子数组最大和
    static long maxKSegments(long[] a, int N, int K) {
        final long NEG = -(1L << 60); // 足够小的负无穷，避免溢出
        // 1-based
        long[] arr = new long[N + 1];
        System.arraycopy(a, 0, arr, 1, N);

        long[] dpPrev = new long[N + 1]; // dp[0][i] = 0
        for (int k = 1; k <= K; k++) {
            long[] end = new long[N + 1];
            long[] dpCurr = new long[N + 1];
            Arrays.fill(end, NEG);
            Arrays.fill(dpCurr, NEG);
            for (int i = 1; i <= N; i++) {
                // 第 k 段以 i 结尾：延长或新开
                long extend = end[i - 1] + arr[i];
                long startNew = dpPrev[i - 1] + arr[i];
                end[i] = Math.max(extend, startNew);
                // 全局最优
                dpCurr[i] = Math.max(dpCurr[i - 1], end[i]);
            }
            dpPrev = dpCurr;
        }
        return dpPrev[N];
    }

    // 简单高效的输入
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) { this.in = is; }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        long nextLong() throws IOException {
            int c, sign = 1;
            long val = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sign = -1; c = read(); }
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int N = (int) fs.nextLong();
        int K = (int) fs.nextLong();
        long[] a = new long[N + 1];
        for (int i = 1; i <= N; i++) a[i] = fs.nextLong();
        long ans = maxKSegments(a, N, K);
        System.out.println(ans);
    }
}

C++

// 题意函数放在外部；主函数只负责输入输出
#include <bits/stdc++.h>
using namespace std;

// 计算恰好K段不相交连续子数组的最大和
long long maxKSegments(const vector<long long>& a1, int N, int K) {
    const long long NEG = -(1LL << 60); // 足够小的负无穷
    // 1-based
    vector<long long> a(N + 1);
    for (int i = 1; i <= N; ++i) a[i] = a1[i];

    // dpPrev[i] = dp[k-1][i]，k=0 时 dp[0][i]=0
    vector<long long> dpPrev(N + 1, 0);

    for (int k = 1; k <= K; ++k) {
        vector<long long> end(N + 1, NEG);   // end[k][i]
        vector<long long> dpCurr(N + 1, NEG); // dp[k][i]
        for (int i = 1; i <= N; ++i) {
            // 第 k 段以 i 结尾：延长或新开
            long long extend = end[i - 1] + a[i];
            long long startNew = dpPrev[i - 1] + a[i];
            end[i] = max(extend, startNew);
            // 全局最优：不以 i 结尾或以 i 结尾
            dpCurr[i] = max(dpCurr[i - 1], end[i]);
        }
        dpPrev.swap(dpCurr);
    }
    return dpPrev[N];
}

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

题面描述

给定一个长度为 $N$ 的整数数组 $a_1,a_2,\dots,a_N$，请从中选择恰好 $K$ 个互不相交、非空的连续子数组，使得它们的元素和之和最大，并输出该最大和。

输入格式

• 第一行两个整数 $N, K$，分别表示数组长度与需要选择的连续子数组个数。
• 第二行包含 $N$ 个整数，表示数组元素 $a_i$。

输出格式

输出一个整数，表示选择恰好 $K$ 段后的最大总和。

数据范围

• $1 \le K \le N \le 10^3$
• $|a_i| \le 10^9$
• 结果保证在 64 位有符号整数范围内。

输入样例

5 2
1 -2 3 5 -1

输出样例

9

样例说明： 选择两段 $[1]$ 与 $[3,5]$，总和为 $1 + (3+5) = 9$。