#P4423. 最大子数组和问题-最大k段和
-
1000ms
Tried: 1
Accepted: 1
Difficulty: 6
最大子数组和问题-最大k段和
解题思路
本题是经典的“恰好选 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 的整数数组 a1,a2,…,aN,请从中选择恰好 K 个互不相交、非空的连续子数组,使得它们的元素和之和最大,并输出该最大和。
输入格式
- 第一行两个整数 N,K,分别表示数组长度与需要选择的连续子数组个数。
- 第二行包含 N 个整数,表示数组元素 ai。
输出格式
输出一个整数,表示选择恰好 K 段后的最大总和。
数据范围
- 1≤K≤N≤103
- ∣ai∣≤109
- 结果保证在 64 位有符号整数范围内。
输入样例
5 2
1 -2 3 5 -1
输出样例
9
样例说明: 选择两段 [1] 与 [3,5],总和为 1+(3+5)=9。