Helping the Nature (Codeforces 1700C)
Tags: Greedy, data structures

Little Leon lives in the forest. He has recently noticed that some trees near his favourite path are withering, while the other ones are overhydrated so he decided to learn how to control the level of the soil moisture to save the trees.There are $$$n$$$ trees growing near the path, the current levels of moisture of each tree are denoted by the array $$$a_1, a_2, \dots, a_n$$$. Leon has learned three abilities which will help him to dry and water the soil.  Choose a position $$$i$$$ and decrease the level of moisture of the trees $$$1, 2, \dots, i$$$ by $$$1$$$.  Choose a position $$$i$$$ and decrease the level of moisture of the trees $$$i, i + 1, \dots, n$$$ by $$$1$$$.  Increase the level of moisture of all trees by $$$1$$$. Leon wants to know the minimum number of actions he needs to perform to make the moisture of each tree equal to $$$0$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$)  — the number of test cases. The description of $$$t$$$ test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — the initial levels of trees moisture. It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$200\,000$$$.

Output: For each test case output a single integer — the minimum number of actions. It can be shown that the answer exists.

Note: In the first test case it's enough to apply the operation of adding $$$1$$$ to the whole array $$$2$$$ times. In the second test case you can apply the operation of decreasing $$$4$$$ times on the prefix of length $$$3$$$ and get an array $$$6, 0, 3$$$. After that apply the operation of decreasing $$$6$$$ times on the prefix of length $$$1$$$ and $$$3$$$ times on the suffix of length $$$1$$$. In total, the number of actions will be $$$4 + 6 + 3 = 13$$$. It can be shown that it's impossible to perform less actions to get the required array, so the answer is $$$13$$$. 

Sample Inputs:
4
3
-2 -2 -2
3
10 4 7
4
4 -4 4 -4
5
1 -2 3 -4 5

Sample Outputs:
2
13
36
33

Solution (Python):
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def solution(n, a):
    diff = []
    for i in range(n - 1):
        diff.append(a[i + 1] - a[i])
    left_dec = 0
    right_dec = 0
    for d in diff:
        if d > 0:
            right_dec += d
        elif d < 0:
            left_dec += -d
    level_posn = a[0] - left_dec
    return left_dec + right_dec + abs(level_posn)
tests = inp()
for test in range(tests):
    n = inp()
    a = inlt()
    print(solution(n, a))

Solution (Python):
import sys
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def solution(n, a):
    diff = []
    for i in range(n - 1):
        diff.append(a[i + 1] - a[i])
    left_dec = 0
    right_dec = 0
    for d in diff:
        if d > 0:
            right_dec += d
        elif d < 0:
            left_dec += -d
    level_posn = a[0] - left_dec
    return left_dec + right_dec + abs(level_posn)
tests = inp()
for test in range(tests):
    n = inp()
    a = inlt()
    print(solution(n, a))

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    curr = arr[0]
    ans = 0
    for i in range(n - 1):
        if curr <= arr[i + 1]:
            curr = arr[i + 1]
        else:
            ans += curr - arr[i + 1]
            curr = arr[i + 1]
    f = arr[0] - ans
    b = arr[-1]
    if f < 0:
        ans += abs(f)
        b += abs(f)
    return b + ans
for _ in range(int(input())):
    print(solve())