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