Consider an operation where you choose a contiguous subarray and a positive integer x, then add x to every element of that subarray. The cost of one operation equals x.
Given that you can perform this operation any number of times, return the minimum total cost needed to make nums non-decreasing.
Examples
Example 1
Input: nums = [3,4,1,6,2]
Output: 7
Explanation: Adding 3 to the subarray [1,6,2] gives [3,4,4,9,5] at a cost of 3. Adding 4 to the last element gives [3,4,4,9,9], which is non-decreasing, at an added cost of 4. The total cost is 7, and no cheaper sequence of operations reaches a non-decreasing array.
Example 2
Input: nums = [1,2,3]
Output: 0
Explanation: nums is already non-decreasing, so no operations are needed.
Example 3
Input: nums = [5,4,3,2,1]
Output: 4
Explanation: Each of the four adjacent pairs drops by 1, and raising each element to match the one before it costs 1 per pair, for a total of 4.
Constraints
1≤nums.length≤105
1≤nums[i]≤109
Examples
Example 1
Input
nums = [3, 4, 1, 6, 2]
Output
7
Example 2
Input
nums = [1, 2, 3]
Output
0
Example 3
Input
nums = [5, 4, 3, 2, 1]
Output
4
Loading editor...
Run checks the sample cases; Submit runs every case.
Samples 3
Custom 0
passedwrong answertime limiterrorran, no expected valuenot run