Toggle navigation
首页
讨论版
入门知识
题库
状态
排名
竞赛&作业
下载
Login
问题 1981. -- k个最大连续子序列和
1981: k个最大连续子序列和
时间限制:
1 Sec
内存限制:
128 MB
提交:
17
解决:
9
[
提交
][
状态
][
讨论版
]
题目描述
k个最大连续子序列和问题,即在一个长度为N的数列中,求k个连续子序列,使得这k个连续子序列的和最大,且k个子序列无公共元素。
即给定由n个整数(可能为负整数)组成的序列a1,a2,…, an,(-100≤ai≤100),以及一个正整数k,要求确定序列a1,a2,…,an的k个不相交的子段,使这k个子段的总和达到最大。
输入
第一行:n,k(1≤n ≤1000,2≤k≤10)
第二行:a1,a2,… an每个数中间以空格分隔。
输出
k个子段的最大和。
样例输入
10 2 -1 1 -2 3 4 -2 -5 5 6 7
样例输出
25
提示
来源
动态规划
[
提交
][
状态
]