花环(garland)
题目描述
Kiana有一个漂亮的花环,花环上有n朵五颜六色的花儿,这些花儿构成了一个环形的结构,沿顺时针方向依次编号为1,2,⋯,n,且第n朵花儿与第1朵花儿也是相邻的。
Kiana的小伙伴们都喜欢花儿,于是Kiana决定献出自己的花环,把花儿分给自己的朋友。具体而言,Kiana共有m个小伙伴,故她希望在花环上剪下m段连续的区间来,每个区间可以包含任意多朵花儿,但每朵花儿至多属于一个区间。
当然,并非每朵花儿都讨Kiana喜爱,于是她给了每朵花儿一个魅力值,其中有些好看的花儿魅力值就为正数,有些Kiana觉得不好看的花儿魅力值就为负数。
Kiana希望自己剪下来送给小伙伴的花儿的魅力值总和尽可能大,并想求出这个最大值是多少。由于Kiana自己不会算,所以希望你能够帮助她。
输入输出格式
输入格式
第一行包含两个正整数n和m,分别表示花环上花儿的数量与Kiana的小伙伴数量。
第二行包含n个整数,其中第i个整数Fi表示第i朵花儿的魅力值。数据保证至少有m朵花儿的魅力值是正数,即Kiana最后得到的魅力值总和总是可以大于0的。
输出格式
输出一行一个正整数,表示Kiana能够剪下来的花儿的最大魅力值总和。
输入输出样例
输入样例#1:
输出样例#1:
输入样例#2:
garland2.in
输出样例#2:
garland2.ans
输入样例#3:
garland3.in
输出样例#3:
garland3.ans
输入样例#4:
garland4.in
输出样例#4:
garland4.ans
输入样例#5:
garland5.in
输出样例#5:
garland5.ans
样例解释
Kiana的花环上共有10朵花儿,其魅力值依次为−1,6,−2,7,−3,8,−4,9,−5,10,Kiana需要从中选出3个区间来送给自己的小伙伴。那么,Kiana会选择第10,1,2,3,4朵花构成的区间和第6朵、第8朵花单独构成的两个区间,第1个区间的魅力值为10+(−1)+6+(−2)+7=20,后两个区间的魅力值分别为8和9,故总的魅力值为20+8+9=37,可以证明这是魅力值最大的选择方案。
数据范围
对于25%的数据,保证1≤n≤30,1≤m≤10。
对于50%的数据,保证1≤n≤3000,1≤m≤1000。
对于100%的数据,保证1≤n≤3×105,1≤m≤105,−100≤Fi≤100且Fi=0。
上面每一档数据内部,各有20%的数据保证m=1,还有20%的数据保证m=2,另有20%的数据保证m≤10。