Tap here to switch tabs
Problem
Submissions

Problem: Find Maximum Value in a Constrained Sequence

Find Maximum Value in a Constrained Sequence asks for the greatest value in an array starting at zero, with step limits between neighbors and upper bounds at specified indices.

Statement

You want to construct an array a of length n with indices from 00 to n −1- 1 such that:

  • a[0] =0= 0

  • The absolute difference between any two adjacent elements satisfies ∣| a[i + 1] −- a[i] ∣≤| \leq diff[i] for all 0≤i<0 \leq i < n −1- 1.

  • For each condition in restrictions, represented as [idx,maxVal][idx, maxVal], the element at index idx satisfies a[idx] ≤maxVal\leq maxVal.

Return the maximum possible value that can be achieved in the array a.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • 1≤1 \leq restrictions.length ≤\leq n −1- 1

  • restrictions[i].length =2= 2

  • restrictions[i] =[idx,maxVal]= [idx, maxVal]

  • 1≤idx<1 \leq idx < n

  • 1≤maxVal≤1061 \leq maxVal \leq 10^6

  • diff.length == n −1- 1

  • 1≤1 \leq diff[i] ≤10\leq 10

  • The values of restrictions[i][0] are unique.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Find Maximum Value in a Constrained Sequence

Find Maximum Value in a Constrained Sequence asks for the greatest value in an array starting at zero, with step limits between neighbors and upper bounds at specified indices.

Statement

You want to construct an array a of length n with indices from 00 to n −1- 1 such that:

  • a[0] =0= 0

  • The absolute difference between any two adjacent elements satisfies ∣| a[i + 1] −- a[i] ∣≤| \leq diff[i] for all 0≤i<0 \leq i < n −1- 1.

  • For each condition in restrictions, represented as [idx,maxVal][idx, maxVal], the element at index idx satisfies a[idx] ≤maxVal\leq maxVal.

Return the maximum possible value that can be achieved in the array a.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • 1≤1 \leq restrictions.length ≤\leq n −1- 1

  • restrictions[i].length =2= 2

  • restrictions[i] =[idx,maxVal]= [idx, maxVal]

  • 1≤idx<1 \leq idx < n

  • 1≤maxVal≤1061 \leq maxVal \leq 10^6

  • diff.length == n −1- 1

  • 1≤1 \leq diff[i] ≤10\leq 10

  • The values of restrictions[i][0] are unique.