《算法竞赛宝典》基础算法艺术(公开课程)

【题目描述】k个最大连续子序列和(ksum.cpp/c/pas)

　　张琪曼进一步研究k个最大连续子序列和问题，即在一个长度为N的数列中，求k个连续子序列，使得这k个连续子序列的和最大，且k个子序列无公共元素。

　　即给定由n个整数（可能为负整数）组成的序列a₁，a₂，…， a_n，(－100≤a_i≤100)，以及一个正整数k，要求确定序列a₁，a₂，…，a_n的k个不相交的子段，使这k个子段的总和达到最大。

　　【输入格式】

　　第一行：n，k（1≤n ≤1000，2≤k≤10）

　　第二行：a₁，a₂，… a_n每个数中间以空格分隔。

　　【输出格式】

　　k个子段的最大和。

　　【样例输入】

　　10 2

　　-1 1 -2 3 4 -2 -5 5 6 7

　　【样例输出】

　　25