Dwendwen给大佬分组

Time Limit
10s
Memory Limit
262144KB
Judge Program
Standard
Ratio(Solve/Submit)
5.88%(3/51)
Description:

众所周知,实验室的同学们都是大佬。现在实验室共有N位大佬,为了发挥大佬们的辐射能力,Dwendwen准备按座位将其分为k个学习小组。

为了简化问题,我们假设实验室的座位是一种长度为N(N个座位)的线状结构,坐在第i个位置的大佬有影响力ai。在不能调整座位的前提下,Dwendwen需要将大佬们分为k组,其中每个组内的大佬都是座位连续的。一个小组的战斗力为小组所有大佬中,最大影响力与最小影响力之差,即max(a)-min(a)。

现在Dwendwen希望让实验室k个小组的总战斗力最大化,你能帮帮他吗?

Input:

第一行为两个空格分割的整数N(1≤N≤10000)和k(1≤k≤N),分别表示实验室人数和小组个数。

第二行为N个空格分割的正整数,第i个数字ai(1≤ai≤500000)为坐在第i个位置的大佬的影响力。

Output:

实验室所有小组的总战斗力的最大值。

Sample Input:
5 1
2 4 5 6 3
Sample Output:
4

Submit