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:3Explanation: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:4Explanation:(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:7Explanation:(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;
}
}
```