问题1002--幼儿园

1002: 幼儿园

时间限制: 1 Sec  内存限制: 128 MB
提交: 121  解决: 33
[提交] [状态] [讨论版] [命题人:]

题目描述

在幼儿园里,老师让小朋友站成一条线,每连续几个人要分成一组,这个分组有个原则,希望组里的小朋友差异度最大。这个差异度是这样定义的,每个小朋友有一个个性值,一个小组的差异度为这个小组中最大个性值减最小个性值。问怎样分组,可以使得所有分组的差异度之和最大,输出这个最大差异度之和。

输入

输入n,表示有n个小朋友

然后一行输入n个整数ai,表示每个小朋友的个性值

输出

输出最大差异度之和

样例输入 Copy

5
1 2 3 1 2

样例输出 Copy

3

提示

【样例说明】

可以【1 2 3】【1 2】分,差异度之和为2+1=3

也可以【1 2】【3 1 2】分,差异度之和为1+2=3

其他样例:

输入:

3

3 3 3

输出:

0

【数据规模和约定】

1<=n<=10^6

-10^9<=ai<=10^9

来源/分类

cf484D