#3796

Find Maximum Value in a Constrained Sequence

specialist · 695 · lc medium +30 · 62% accepted · 76 likes · top 63%

Description

Given an integer n, an integer array diff of length n-1, and a 2D array restrictions where each entry [idx, maxVal] caps a[idx] <= maxVal, construct a non-negative sequence a of length n with a[0] = 0 and |a[i] - a[i+1]| <= diff[i] for all consecutive pairs, choosing values to maximize the largest element in a, and return that maximum value.

Code

1

2

3

class Solution:
    def findMaxVal(self, n: int, restrictions: List[List[int]], diff: List[int]) -> int:

class Solution:
    def findMaxVal(self, n: int, restrictions: List[List[int]], diff: List[int]) -> int: