Codeforces Round #276 (Div. 1)D（贪心+dp）_html/css_WEB-ITnose

D. Kindergarten

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

In a kindergarten, the children are being divided into groups. The teacher put the children in a line and associated each child with his or her integer charisma value. Each child should go to exactly one group. Each group should be a nonempty segment of consecutive children of a line. A group's sociability is the maximum difference of charisma of two children in the group (in particular, if the group consists of one child, its sociability equals a zero).

The teacher wants to divide the children into some number of groups in such way that the total sociability of the groups is maximum. Help him find this value.

Input

The first line contains integer n ? the number of children in the line (1?≤?n?≤?106).

The second line contains n integers ai ? the charisma of the i-th child (?-?109?≤?ai?≤?109).

Output

Print the maximum possible total sociability of all groups.

Sample test(s)

input

51 2 3 1 2

output

input

33 3 3

output

Note

In the first test sample one of the possible variants of an division is following: the first three children form a group with sociability 2, and the two remaining children form a group with sociability 1.

In the second test sample any division leads to the same result, the sociability will be equal to 0 in each group.

题意：给出n个数，要求你把它分成若干个连续的区间，每个区间的权值定义为该区间最大值与最小值的差值，最后求所有区间的最大权值和

思路：写这个题解前先吐槽一下自己，自从区域赛回来以后忙各种杂事，好久没刷题了，就拿这道不怎么难的题来说，想了好久

最后还是看别人代码才写出来也是弱成狗，想每天安安静静的做题都不行，生活就是这样啊，何时才成达成自己的目标履行自己的诺言，好了，槽点吐完，下面是题解

首先注意到，划分的区间一定满足单调性，这是一种贪心思想，然后就是dp了

dp[i]表示前i个数的最优值

如果a[i-2]a[i] dp[i]=max(dp[i-2]+a[i-1]-a[i],dp[i-1])

如果a[i-2]>a[i-1]>a[i] dp[i]=dp[i-1]+a[i-1]-a[i]

还有其它几种情况类似~