In this problem, you are given an integer array and you need to perform some operations on the array to make all the elements equal to 0. In one operation, you can select a prefix of the given array and increment or decrement all the elements of the prefix by 1.
You have an array, arr, consisting of n integers. Find the minimum number of operations required to convert every element of this array to 0.
A prefix is a contiguous group of items that includes the first element in the cart. For example, [1], [1, 2], [1, 2, 3] etc are prefixes of [1, 2, 3, 4, 5].
Note: It is guaranteed that it is always possible to convert every element of the array to 0.
✎﹏Credit to ⟡ Sndix ⟡ 🦋
Example 1:
Input: arr = [3, 2, 1]
Output: 3
Explanation:For the input arr, the most efficient approach is:Operation 1: Let the prefix length be 2, and decrement by 1. Cart after this operation is [2, 1, 1] Operation 2: Let the prefix length be 1, and decrement by 1. Cart after this operation is [1, 1, 1] Operation 3: Let the prefix length be 3, and decrement by 1. Cart after this operation is [0, 0, 0] So the enswer is 3. Note that it is not possible to make all the elements of the arry 0 in fewer operations.
Unknown for now
input:
output: