arrays - 使用数组中左右索引给出的约束最大化权重总和

Question

我最近遇到了一个有趣的编码问题，如下:

有n个盒子，我们假设这是一个n个盒子的数组。

对于这个数组的每个索引i，给出三个值-

1.) 权重(i)

2.) 左(i)

3.) 右(i)

left(i) 表示 - 如果选择了 weight[i]，我们将不允许从中选择 left[i] 元素此 第 i 个元素 的左侧。

同样，right[i] 表示如果选择arr[i]，则不允许我们选择right[i] 元素从它的右边开始。

示例:

重量[2] = 5

左[2] = 1

右[2] = 3

然后，如果我在位置 2 选择元素，我会得到 5 个单位的权重。但是，我无法在位置 {1} 处选择元素(由于左约束)。并且不能在位置 {3,4,5} 拾取元素(由于右约束)。

目标 - 我们需要计算我们可以选择的权重的最大总和。

示例测试用例:-

**输入:**

5

2 0 3

4 0 0

3 2 0

7 2 1

9 2 0

**输出:**

13

注意 - 第一列是权重，第二列是左约束，第三列是右约束

我使用动态规划方法(类似于最长递增子序列)来达到O(n^2) 的解决方案。但是，想不出 O(n*logn) 解决方案。 (n 最大为 10^5。)

我还尝试使用优先级队列，其中(right[i] + i)值较低的元素被赋予较高的优先级(assigned higher priority to element具有较低的“i”值，以防主键值相等)。但是，它也给出了超时错误。

还有其他方法吗？或优先队列方法的任何优化？如果需要，我可以发布我的两个代码。谢谢。

Answer 1

一种方法是使用 binary indexed tree创建一个数据结构，使每次在 O(logn) 时间内执行两个操作变得容易:

1. 将数字插入数组
2. 找到给定范围内的最大值

我们将使用此数据结构来保存通过选择框 i 以及左侧框的最佳选择可以获得的最大权重。

关键是我们只会在到达满足正确约束的点时才将值插入此数据结构。

要找到框 i 的最佳值，我们需要在数据结构中找到位置 i-left[i] 之前所有点的最大值，这可以在 O(logn) 中完成。

最终的算法是遍历 i=0..n-1 并且对于每个 i:

1. 通过在范围 0..(i-left[i]) 中找到最大值来计算框 i 的结果
2. 安排当我们到达位置 i+right[i] 时要添加的结果
3. 将任何先前安排的结果添加到我们的数据结构中

最终的结果是整个数据结构中的最大值。

总体而言，复杂度为 o(nlogn)，因为 i 的每个值都会导致一次查找和一次更新操作。