Kindergarten (Codeforces 484D)
Tags: Greedy, data structures

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.

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.

Sample Inputs:
5
1 2 3 1 2

3
3 3 3

Sample Outputs:
3

0

Solution (Python):
n = int(input())
a = input().split(' ')
a += [0]
m1 = int(a[0])
m2 = -int(a[0])
f = [0] * n
for i in range(0, n):
    f[i] = max(m1 - int(a[i]), m2 + int(a[i]))
    m1 = max(m1, f[i] + int(a[i + 1]))
    m2 = max(m2, f[i] - int(a[i + 1]))
print(f[n - 1])

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
dp = [0] * n
(pos, neg) = (-10 ** 18, -10 ** 18)
for (i, x) in enumerate(a):
    prv = 0 if i == 0 else dp[i - 1]
    dp[i] = max(neg + x, pos - x, prv)
    pos = max(pos, prv + x)
    neg = max(neg, prv - x)
print(dp[-1])

Solution (Python):
n = int(input())
if n == 1:
    print(0)
else:
    a = [0] * (n + 1)
    i = 1
    for v in map(int, input().split()):
        a[i] = v
        i += 1
    dp = [0] * (n + 1)
    dp[2] = abs(a[1] - a[2])
    for i in range(3, n + 1):
        if a[i - 2] < a[i - 1] and a[i - 1] < a[i] or (a[i - 2] > a[i - 1] and a[i - 1] > a[i]):
            dp[i] = dp[i - 1] + abs(a[i] - a[i - 1])
        else:
            dp[i] = max(dp[i - 1], dp[i - 2] + abs(a[i] - a[i - 1]))
    print(dp[n])