如何在给定的约束下找到数组中可能的最大数量？

Question

我正在解决一个问题，我需要构造一个大小为 N 的数组，以便该数组遵守以下约束：

数组的第一个元素始终为 0 (arr[0] = 0)。 相邻元素之间的差值小于或等于 1 (|arr[i] - arr[i-1]| <= 1). We are given M pairs (x, y), which specify that the value at index x cannot exceed y (arr[x] <= y). All the values of array must be positive integers Given these constraints, I need to determine the maximum possible value in the array.

以下是一些示例测试用例：

N = 5，M = 4，具有 (1, 0)、(2, 0)、(3, 0)、(4, 0) 对 可能的数组：[0, 0, 0, 0, 0] 答案：0

N = 5，M = 1，有对 (3, 0) 可能的数组：[0, 1, 1, 0, 1] 答案：1

N = 10，M = 1，有对 (3, 1) 可能的数组：`[0, 1, 2, 1,2,3,4,5,6] 答案是 6

第四个测试用例 N = 10，M = 2 (1,1) (3,4)

数组：[0,1,2,3,4]答案是4

我尝试过，但在一些测试用例上失败了

示例： N = 10，M = 3 (3,20) (7,50) (9,1)

Answer 1

这有点缺乏完整的答案，但仍然是一个强有力的提示。

---

为了简单起见，让我们首先考虑一个在从 0 到 N（含）的每个整数点处都有约束的版本。

所以，我们有以下问题：

arr[0]   <= 0
arr[1]   <= v[1]
arr[2]   <= v[2]
...
arr[N-1] <= v[N-1]
arr[N]   <= infinity

为了完整性，我们添加

arr[0] <= 0

，如果 x = N 处没有其他约束，则添加

arr[N] <= infinity

。

现在，考虑每一点的条件：

arr[x]   <= arr[x-1] + 1
arr[x]   <= arr[x+1] + 1

事实证明，只需对数组进行两次传递即可满足这些要求。

第一遍将从左到右，我们将满足前一个约束。 当我们到达 x 点时，从 1 到 x-1 的所有左侧约束都已合并到 arr[x-1] 的单个值中。

for i = 1, 2, ..., N:
    arr[i] := min (arr[i], arr[i - 1] + 1)

第二遍将从右到左，我们将满足后一个约束。 当我们到达点 x 时，从 x+1 到 N 的所有右侧约束都已合并到 arr[x+1] 的单个值中。

for i = N, N-1, ..., 1:
    arr[i] := min (arr[i], arr[i + 1] + 1)

要找到最大值，只需迭代数组即可。

---

原始问题仅在某些点具有约束。 也许解决方案应该花费点数的线性时间。

因此，我们不会考虑所有整数点，而是编写类似的左侧和右侧条件，但以前一个和下一个给定点为特色。 为了完整性，我们应该在 x=0 处添加零，并在 x=N 处添加无穷大。 两次通过就足够了。

要找到最大值，首先迭代数组。 此外，考虑两个连续给定点之间每个段上的最高可能点：每个这样的段都是可在恒定时间内解决的子问题。