解题思路

要求在保持原相对顺序的前提下，从长度为 $n$ 的数组中恰好选出 $k$ 个元素，使其和最大。设

转移分两类（划分型动态规划的典型“选/不选当前元素”）：

• 不选第 $i$ 个：$dp[i-1][j]$
• 选第 $i$ 个：$dp[i-1][j-1] + a_i$

于是

边界与不可行状态：

• $dp[0][0]=0$
• 对所有 $i\ge 0$，$dp[i][0]=0$（选 0 个和为 0）
• 当 $j>i$ 或 $j<0$ 时不可行，赋为 $-\infty$（实现中用很小的负数代替）

答案为 $dp[n][k]$。

复杂度分析

• 时间复杂度：每个状态只计算一次，规模为 $O(nk)$。
• 空间复杂度：保存整个二维表，规模为 $O(nk)$。

代码实现

Python

# 题面功能放在外部函数中，主函数只负责输入输出
from typing import List

def max_k_sum_2d(a: List[int], k: int) -> int:
    n = len(a)
    NEG = -10**15  # 充当 -∞（足够小，避免与真实和混淆）
    # dp[i][j]：前 i 个数中选 j 个的最大和（i, j 含义见题解）
    dp = [[NEG] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    for i in range(1, n + 1):
        dp[i][0] = 0  # 选 0 个恒为 0
        for j in range(1, k + 1):
            if j > i:
                # 前 i 个里不可能选出 j 个，保持 -∞
                continue
            # 不选第 i 个 or 选第 i 个（数组下标为 i-1）
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i - 1])
    return dp[n][k]

def main():
    import sys
    data = sys.stdin.read().strip().split()
    n, k = map(int, data[:2])
    arr = list(map(int, data[2:2 + n]))
    print(max_k_sum_2d(arr, k))

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main（ACM 风格）
import java.util.*;

public class Main {
    // 外部函数：二维 DP 实现
    static long maxKSum2D(int[] a, int k) {
        int n = a.length;
        long NEG = Long.MIN_VALUE / 4; // 充当 -∞，/4 防止加法溢出
        long[][] dp = new long[n + 1][k + 1];
        // 初始化为 -∞
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], NEG);
        }
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = 0; // 选 0 个恒为 0
            for (int j = 1; j <= k; j++) {
                if (j > i) {
                    // 不可行，保持 -∞
                    continue;
                }
                // 不选第 i 个 or 选第 i 个（注意 a 的下标 i-1）
                long notPick = dp[i - 1][j];
                long pick = (dp[i - 1][j - 1] == NEG) ? NEG : dp[i - 1][j - 1] + a[i - 1];
                dp[i][j] = Math.max(notPick, pick);
            }
        }
        return dp[n][k];
    }

    public static void main(String[] args) {
        // 数据范围不大，直接用 Scanner
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        System.out.println(maxKSum2D(a, k));
        sc.close();
    }
}

C++

// ACM 风格：主函数读写，功能放到外部函数
#include <bits/stdc++.h>
using namespace std;

// 二维 DP：dp[i][j] = 前 i 个数中选 j 个的最大和
long long maxKSum2D(const vector<long long>& a, int k) {
    int n = (int)a.size();
    const long long NEG = (long long)-4e18; // 充当 -∞，避免溢出
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, NEG));
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
        dp[i][0] = 0; // 选 0 个恒为 0
        for (int j = 1; j <= k; ++j) {
            if (j > i) continue; // 不可行，保持 -∞
            long long notPick = dp[i - 1][j];
            long long pick = (dp[i - 1][j - 1] == NEG) ? NEG : dp[i - 1][j - 1] + a[i - 1];
            dp[i][j] = max(notPick, pick);
        }
    }
    return dp[n][k];
}

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

题面描述

给定一个长度为$n$的数组$[a_1,a_2,...,a_n]$，问从中选出$k$ 个元素的最大和是多少？

注:不允许改变数组本身的顺序。使用课上学习的划分型动态规划方法去实现！

输入输出

输入： 第一行包含两个整数 $n,k$。

第二行包含$n$个整数$a_1,a_2,a_3,...,a_n$

输出： 一行输出一个整数，即从 $a_1,a_2,a_3,...,a_n$ 中选出 $k$ 个元素能得到的最大和

数据范围

• $1 \le n \le 1000$
• $0 \le k \le n$
• $-1000 \le a_i \le 1000$

样例1

输入

3 2
3 1 2

输出

5

说明 选出$[3,2]$ 的和最大，为$3+2=5$

样例2

输入

5 3
-1 -2 -3 4 5

输出

8

说明 选出$[-1,4,5]$ 的和最大，为$-1+4+5=8$