Question
Magical Array Formation
You are a sage working with an array of magical energy levels.
You are given an integer array target. You also have an array initial of the same size, where all elements start at 0.
In one magical operation, you may choose any continuous subarray of initial and increase every value in that subarray by 1.
Your task is to return the minimum number of magical operations needed to transform initial into target.
Input
The first line of input takes an integer n representing the size of the array target.
The second line of input will take n space-separated integers representing elements of array target.
The second line of input will take n space-separated integers representing elements of array target.
Output
Print the minimum number of magical operations to form a target array from the initial.
Example
Input:
5
1 2 3 2 1
Output:
3
Explanation:
target = [1,2,3,2,1]
We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.
Input:
4
3 1 1 2
Output:
4
Explanation:
target = [3,1,1,2]
[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2]
5
1 2 3 2 1
Output:
3
Explanation:
target = [1,2,3,2,1]
We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.
Input:
4
3 1 1 2
Output:
4
Explanation:
target = [3,1,1,2]
[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2]