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

1/**
2 * [1526] Minimum Number of Increments on Subarrays to Form a Target Array
3 *
4 * You are given an integer array target. You have an integer array initial of the same size as target with all elements initially zeros.
5 * In one operation you can choose any subarray from initial and increment each value by one.
6 * Return the minimum number of operations to form a target array from initial.
7 * The test cases are generated so that the answer fits in a 32-bit integer.
8 *  
9 * Example 1:
10 * 
11 * Input: target = [1,2,3,2,1]
12 * Output: 3
13 * Explanation: We need at least 3 operations to form the target array from the initial array.
14 * [<u>0,0,0,0,0</u>] increment 1 from index 0 to 4 (inclusive).
15 * [1,<u>1,1,1</u>,1] increment 1 from index 1 to 3 (inclusive).
16 * [1,2,<u>2</u>,2,1] increment 1 at index 2.
17 * [1,2,3,2,1] target array is formed.
18 * 
19 * Example 2:
20 * 
21 * Input: target = [3,1,1,2]
22 * Output: 4
23 * Explanation: [<u>0,0,0,0</u>] -> [1,1,1,<u>1</u>] -> [<u>1</u>,1,1,2] -> [<u>2</u>,1,1,2] -> [3,1,1,2]
24 * 
25 * Example 3:
26 * 
27 * Input: target = [3,1,5,4,2]
28 * Output: 7
29 * Explanation: [<u>0,0,0,0,0</u>] -> [<u>1</u>,1,1,1,1] -> [<u>2</u>,1,1,1,1] -> [3,1,<u>1,1,1</u>] -> [3,1,<u>2,2</u>,2] -> [3,1,<u>3,3</u>,2] -> [3,1,<u>4</u>,4,2] -> [3,1,5,4,2].
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	1 <= target.length <= 10^5
35 * 	1 <= target[i] <= 10^5
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
41// discuss: https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn min_number_operations(target: Vec<i32>) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_1526() {
59    }
60}
61