题解

令数组下标从 1 开始，x = nums[i]。定义三维状态：

• dp[i][j][1]：处理到第 i 个元素后，已选 j 段，当前不在子段内 的最大和。
• dp[i][j][2]：处理到第 i 个元素后，已选 j 段，当前位于第 j 段内 的最大和（且该段包含第 i 个元素）。

初始化（i=0 表示未处理任何元素）：

• dp[0][0][1] = 0
• 其余全部置为 -∞（不可达）

转移：

• 不选第 i 个元素（休息态） dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][2])

• 选第 i 个元素（在段内）

  dp[i][j][2] = max(
      dp[i-1][j][2] + x,       // 继续当前第 j 段
      dp[i-1][j-1][1] + x,     // 上一步休息，i 处开启第 j 段
      dp[i-1][j-1][2] + x      // 上一步仍在第 j-1 段，i-1 结束、i 立刻开启第 j 段（无缝衔接）
  )
  

最后答案：max(dp[n][k][1], dp[n][k][2])。

C++ 实现

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

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];

    const long long NEG = (long long)-4e18;
    // dp[i][j][1/2]
    vector<vector<array<long long,3>>> dp(n + 1, vector<array<long long,3>>(k + 1));
    // init to -inf
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= k; ++j)
            dp[i][j] = {NEG, NEG, NEG};

    dp[0][0][1] = 0;

    for (int i = 1; i <= n; ++i) {
        // j = 0
        dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][0][2]); // 实际上 dp[*][0][2] = -inf
        dp[i][0][2] = NEG; // 选 0 段不可能在段内
        int up = min(i, k);
        for (int j = 1; j <= up; ++j) {
            // 休息态
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][2]);

            // 在段内：允许继续、从休息开新段、或无缝衔接开新段
            long long cand1 = (dp[i-1][j][2] == NEG ? NEG : dp[i-1][j][2] + a[i]);
            long long cand2 = (dp[i-1][j-1][1] == NEG ? NEG : dp[i-1][j-1][1] + a[i]);
            long long cand3 = (dp[i-1][j-1][2] == NEG ? NEG : dp[i-1][j-1][2] + a[i]);
            dp[i][j][2] = max(cand1, max(cand2, cand3));
        }
    }

    cout << max(dp[n][k][1], dp[n][k][2]) << "\n";
    return 0;
}

Python 实现

import sys

def main():
    data = sys.stdin.read().strip().split()
    if not data: 
        return
    it = iter(data)
    n = int(next(it)); k = int(next(it))
    a = [0] + [int(next(it)) for _ in range(n)]

    NEG = -10**18
    # dp[i][j][1/2]，用第三维大小 3（丢弃下标 0）
    dp = [[[NEG]*3 for _ in range(k+1)] for __ in range(n+1)]
    dp[0][0][1] = 0

    for i in range(1, n+1):
        dp[i][0][1] = max(dp[i-1][0][1], dp[i-1][0][2])  # 休息
        dp[i][0][2] = NEG
        up = min(i, k)
        for j in range(1, up+1):
            # 休息态
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][2])
            # 在段内
            x = a[i]
            cand1 = dp[i-1][j][2] + x if dp[i-1][j][2] != NEG else NEG
            cand2 = dp[i-1][j-1][1] + x if dp[i-1][j-1][1] != NEG else NEG
            cand3 = dp[i-1][j-1][2] + x if dp[i-1][j-1][2] != NEG else NEG
            dp[i][j][2] = max(cand1, cand2, cand3)

    print(max(dp[n][k][1], dp[n][k][2]))

if __name__ == "__main__":
    main()

Java 实现

import java.io.*;
import java.util.*;

public class Main {
    static final long NEG = (long)-4e18;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        long[] a = new long[n+1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) a[i] = Long.parseLong(st.nextToken());

        long[][][] dp = new long[n+1][k+1][3];
        // init -inf
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                Arrays.fill(dp[i][j], NEG);
            }
        }
        dp[0][0][1] = 0;

        for (int i = 1; i <= n; i++) {
            dp[i][0][1] = Math.max(dp[i-1][0][1], dp[i-1][0][2]);
            dp[i][0][2] = NEG;
            int up = Math.min(i, k);
            for (int j = 1; j <= up; j++) {
                // rest
                dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j][2]);
                // in segment
                long cand1 = dp[i-1][j][2] == NEG ? NEG : dp[i-1][j][2] + a[i];
                long cand2 = dp[i-1][j-1][1] == NEG ? NEG : dp[i-1][j-1][1] + a[i];
                long cand3 = dp[i-1][j-1][2] == NEG ? NEG : dp[i-1][j-1][2] + a[i];
                dp[i][j][2] = Math.max(cand1, Math.max(cand2, cand3));
            }
        }

        System.out.println(Math.max(dp[n][k][1], dp[n][k][2]));
    }
}

题目描述

给定一个整数数组$nums$和一个整数$k$，要求你从数组中找出 $k$ 个不重叠的子数组，使得这 $k$ 个子数组的元素和最大。注意，子数组的下标必须不重叠。

具体要求如下：

1. 子数组的定义是数组的连续部分。

输入格式

• 第一行输入两个整数 $n$ 和 $k$ ($1 ≤ n ≤ 100$, $1 ≤ k ≤ n$)，分别表示数组的长度和要选取的子数组数量。
• 第二行输入 $n$ 个整数，表示数组 $nums$ 的元素，元素值范围为 ($-1000 ≤ nums[i] ≤ 1000$)。

输出格式

• 输出 $k$ 个不重叠子数组和的最大值。

数据范围

• $1 ≤ n ≤ 100$
• $1 ≤ k ≤ n$
• $-10000 ≤ nums[i] ≤ 10000$

示例

输入

6 2
1 -2 3 4 -1 2

输出

9