燃灵之链

【题目描述】

战栗吧！丧钟已为你鸣响！

颤抖吧！挽歌已为你宣唱！

末日审判已经降临,

所有情侣都要付出代价！

情侣教会的暴行激起了广大有良知的单身狗的愤怒，一场起义不可避免的爆发了。

单身狗分裂为两派，左派的FFF和右派的SOX。

FFF旨在烧死一切情侣，但是他们缺乏火源。

你作为一名FFF的团员，接受命令寻找传说中的具有火焰魔法能量的燃灵之链。

然而，当你找到燃灵之链时，却发现燃灵之链的一部分受到了恶魔能量的腐蚀，即所谓负能量，

一部分仍然拥有正能量，为了满足K个起义军团的需要，你需要在含有n个能量子的项链中选取K个互不相邻的子项链。

求所能得到的能量的最大值。（相等恶魔能量和正能量可以在数值上抵消）

【输入格式】

第一行，两个正整数n和k

第二行，这条项链从左到右每个能量子的能量值

【输出格式】

一个正整数ans,为最大值

【样例输入】

7 3



5 -1 4 -8 2 -3 5

【样例输出】

 15

【提示】

三个子项链分别为(5,-1,4)(2)(5)

首先我们观察得出：

这条链是一个一叉树

其次要对这棵树进行剖分

所以我们自然想到了树链剖分

百度搜索树链剖分，你值得拥有！

对于 20%的数据，N<=20;K<=10;

对于 70%的数据，N<=1000,K<=100;

对于 100%的数据,N<=10000,K<=1000;

能量子的范围为[-2^15,2^15]

【来源】

在此键入。