3796. Find Maximum Value in a Constrained Sequence Medium

1/**
2 * [3796] Find Maximum Value in a Constrained Sequence
3 *
4 * You are given an integer n, a 2D integer array restrictions, and an integer array diff of length n - 1. Your task is to construct a sequence of length n, denoted by a[0], a[1], ..., a[n - 1], such that it satisfies the following conditions:
5 * 
6 * 	a[0] is 0.
7 * 	All elements in the sequence are non-negative.
8 * 	For every index i (0 <= i <= n - 2), abs(a[i] - a[i + 1]) <= diff[i].
9 * 	For each restrictions[i] = [idx, maxVal], the value at position idx in the sequence must not exceed maxVal (i.e., a[idx] <= maxVal).
10 * 
11 * Your goal is to construct a valid sequence that maximizes the largest value within the sequence while satisfying all the above conditions.
12 * Return an integer denoting the largest value present in such an optimal sequence.
13 *  
14 * <strong class="example">Example 1:
15 * <div class="example-block">
16 * Input: <span class="example-io">n = 10, restrictions = [[3,1],[8,1]], diff = [2,2,3,1,4,5,1,1,2]</span>
17 * Output: <span class="example-io">6</span>
18 * Explanation:
19 * 
20 * 	The sequence a = [0, 2, 4, 1, 2, 6, 2, 1, 1, 3] satisfies the given constraints (a[3] <= 1 and a[8] <= 1).
21 * 	The maximum value in the sequence is 6.
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">n = 8, restrictions = [[3,2]], diff = [3,5,2,4,2,3,1]</span>
26 * Output: <span class="example-io">12</span>
27 * Explanation:
28 * 
29 * 	The sequence a = [0, 3, 3, 2, 6, 8, 11, 12] satisfies the given constraints (a[3] <= 2).
30 * 	The maximum value in the sequence is 12.
31 * </div>
32 *  
33 * Constraints:
34 * 
35 * 	2 <= n <= 10^5
36 * 	1 <= restrictions.length <= n - 1
37 * 	restrictions[i].length == 2
38 * 	restrictions[i] = [idx, maxVal]
39 * 	1 <= idx < n
40 * 	1 <= maxVal <= 10^6
41 * 	diff.length == n - 1
42 * 	1 <= diff[i] <= 10
43 * 	The values of restrictions[i][0] are unique.
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/find-maximum-value-in-a-constrained-sequence/
49// discuss: https://leetcode.com/problems/find-maximum-value-in-a-constrained-sequence/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn find_max_val(n: i32, restrictions: Vec<Vec<i32>>, diff: Vec<i32>) -> i32 {
55        0
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_3796() {
67    }
68}
69