minimum-operations-to-make-array-non-decreasing

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an integer array <code>nums</code> of length <code>n</code>.

In one operation, you may choose any subarray <code>nums[l..r]</code> and increase each element in that subarray by <code>x</code>, where <code>x</code> is any positive integer.

Return the minimum possible sum of the values of <code>x</code> across all operations required to make the array non-decreasing.

An array is non-decreasing if <code>nums[i] &lt;= nums[i + 1]</code> for all <code>0 &lt;= i &lt; n - 1</code>.

&nbsp;
Example 1:

<div class="example-block">
Input: nums = [3,3,2,1]

Output: 2

Explanation:

One optimal set of operations:

<ul>
	<li>Choose subarray <code>[2..3]</code> and add <code>x = 1</code> resulting in <code>[3, 3, 3, 2]</code></li>
	<li>Choose subarray <code>[3..3]</code> and add <code>x = 1</code> resulting in <code>[3, 3, 3, 3]</code></li>
</ul>

The array becomes non-decreasing, and the total sum of chosen <code>x</code> values is <code>1 + 1 = 2</code>.
</div>

Example 2:

<div class="example-block">
Input: nums = [5,1,2,3]

Output: 4

Explanation:

One optimal set of operations:

<ul>
	<li>Choose subarray <code>[1..3]</code> and add <code>x = 4</code> resulting in <code>[5, 5, 6, 7]</code></li>
</ul>

The array becomes non-decreasing, and the total sum of chosen <code>x</code> values is <code>4</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n == nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>