← 返回 amazon 的题目列表Minimum Steps to Zero Array
类型:online_judge
Given a list of integers, you can choose any contiguous sub list from the start to any position at each step and increment or decrement each number in the sublist by 1. The goal is to make the entire list zero in the minimum number of steps. Return the minimum number of steps.
Example
Input: [3, 2, 1]
Output: 3
Explanation
[3, 2, 1] -> [2, 1, 0] (decrement entire array by 1)
[2, 1, 0] -> [1, 0, 0] (decrement first two positions by 1)
[1, 0, 0] -> [0, 0, 0] (decrement first position by 1)
Finally return 3.
Input: [3, 2, 0, 0, -1]
Output: 5
Explanation
[3, 2, 0, 0, -1] -> [4, 3, 1, 1, 0]
[4, 3, 1, 1, 0] -> [3, 2, 0, 0, 0]
[3, 2, 0, 0, 0] -> [2, 1, 0, 0, 0]
[2, 1, 0, 0, 0] -> [1, 0, 0, 0, 0]
[1, 0, 0, 0, 0] -> [0, 0, 0, 0, 0]
Finally return 5.
Example
Input
[3, 2, 1]