Formatted question description: https://leetcode.ca/all/1526.html

# 1526. Minimum Number of Increments on Subarrays to Form a Target Array (Hard)

Given an array of positive integers target and an array initial of same size with all zeros.

Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:

• Choose any subarray from initial and increment each value by one.

The answer is guaranteed to fit within the range of a 32-bit signed integer.

Example 1:

Input: target = [1,2,3,2,1]
Output: 3
Explanation: We need at least 3 operations to form the target array from the initial array.
[0,0,0,0,0] increment 1 from index 0 to 4 (inclusive).
[1,1,1,1,1] increment 1 from index 1 to 3 (inclusive).
[1,2,2,2,1] increment 1 at index 2.
[1,2,3,2,1] target array is formed.


Example 2:

Input: target = [3,1,1,2]
Output: 4
Explanation: (initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target).


Example 3:

Input: target = [3,1,5,4,2]
Output: 7
Explanation: (initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target).


Example 4:

Input: target = [1,1,1,1]
Output: 1


Constraints:

• 1 <= target.length <= 10^5
• 1 <= target[i] <= 10^5

Related Topics:
Segment Tree

## Solution 1.

I found that a small number will break the increments into two parts. For example [2, 1, 2], you can’t increment both the first and last 2 at the same time because there is a smaller number 1 in between. So we need to pay attention to those small numbers.

I also tried to see if it’s possible to resolve this problem using a linear scan, and it turns out working. Take some inputs as examples.

For input [3 1 5]:

• To get 3, we need 3 increments.
• To get 1, since it’s smaller than 3, we can get 1 while getting 3, so we don’t need additional increment.
• To get 5, since 5 is greater than 1, we need 5 - 1 = 4 more increments to get 5.
• In total we need 3 + 0 + 4 increments.

I also verified this algorithm with inputs like [1, 2, 3] and [2, 1, 2] to check the correctness.

The algorithm would be as simple as:

• Linear scan the array.
• For A[i], if it’s greater than A[i - 1], then increment answer by A[i] - A[i - 1]; otherwise, do nothing.
// OJ: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/

// Time: O(N)
// Space: O(1)
class Solution {
public:
int minNumberOperations(vector<int>& A) {
int ans = A[0];
for (int i = 1; i < A.size(); ++i) ans += max(0, A[i] - A[i - 1]);
return ans;
}
};


We can compress it into two lines.

// OJ: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/

// Time: O(N)
// Space: O(1)
class Solution {
public:
int minNumberOperations(vector<int>& A) {
for (int i = A.size() - 1; i > 0; --i) A[i] = max(0, A[i] - A[i - 1]);
return accumulate(begin(A), end(A), 0);
}
};


This would be a one liner in python

# OJ: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/

# Time: O(N)
# Space: O(1)
class Solution:
def minNumberOperations(self, A: List[int]) -> int:
return sum([max(0, x - y) for x, y in zip(A, [0] + A)])


Java

class Solution {
public int minNumberOperations(int[] target) {
int operations = 0;
int prevHeight = 0;
int length = target.length;
for (int i = 0; i < length; i++) {
int height = target[i];
if (height > prevHeight)
operations += height - prevHeight;
prevHeight = height;
}
return operations;
}
}