Minimum Operations to Make Array Non Decreasing
You are given an integer array nums of length n.
In one operation, you may choose any subarray nums[l..r] and increase each element in that subarray by x, where x is any positive integer.
Return the minimum possible sum of the values of x across all operations required to make the array non-decreasing.
An array is non-decreasing if nums[i] <= nums[i + 1] for all 0 <= i < n - 1.
Example 1:
Input: nums = [3,3,2,1]
Output: 2
Explanation:
One optimal set of operations:
• Choose subarray [2..3] and add x = 1 resulting in [3, 3, 3, 2]
• Choose subarray [3..3] and add x = 1 resulting in [3, 3, 3, 3]
The array becomes non-decreasing, and the total sum of chosen x values is 1 + 1 = 2.
Example 2:
Input: nums = [5,1,2,3]
Output: 4
Explanation:
One optimal set of operations:
• Choose subarray [1..3] and add x = 4 resulting in [5, 5, 6, 7]
The array becomes non-decreasing, and the total sum of chosen x values is 4.
Constraints:
• 1 <= n == nums.length <= 105
• 1 <= nums[i] <= 109
class Solution {
public long minOperations(int[] nums) {
long sum = 0;
for (int i = 0; i < nums.length-1; i++) {
if (nums[i] > nums[i+1]) {
long diff = nums[i] - nums[i+1];
for (int l = i+1; l < nums.length; l++) {
nums[l] += diff;
}
sum += diff;
}
}
return sum;
}
}
Test cases:
Case 1:
nums=[3,3,2,1]
Expected: 2
Actual: 2
Case 2:
nums=[5,1,2,3]
Expected: 4
Actual: 4
