使用数组中左右索引给出的约束最大化权重总和
Maximize sum of weights with constraints given on left and right indices in array
我最近遇到了一个有趣的编码问题，如下：
有n个盒子，假设这是一个有n个盒子的数组。
对于这个数组的每个索引i，给出三个值-
1.) 体重(i)
2.) 左(i)
3.) 右(i)
left(i) 意思是 - 如果选择了 weight[i]，我们就不能从这个 ith element.
左边选择 left[i] 个元素
同理，right[i]表示如果选择了arr[i]，则不允许选择其右边的right[i]个元素。
示例：
体重[2] = 5
左[2] = 1
右[2] = 3
然后，如果我在位置 2 选择元素，我得到 5 个单位的权重。但是，我无法在位置 {1} 处选择元素（由于左约束）。并且不能在位置 {3,4,5} 拾取元素（由于右约束）。
Objective - 我们需要计算我们可以选择的权重的最大总和。
示例测试用例：-
**输入：**
5
2 0 3
4 0 0
3 2 0
7 2 1
9 2 0
**输出：**
13
注意 - 第一列是权重，第二列是左约束，第三列是右约束
我使用动态规划方法（类似于最长递增子序列）来得出O(n^2)解。但是，想不出 O(n*logn) 解决方案。 (n can be up to 10^5.)
我也尝试过使用优先级队列，其中(right[i] + i)值较低的元素被赋予较高的优先级（assigned higher priority to element with lower value of "i"，以防主键值相等）。但是，它也给出了超时错误。
还有其他方法吗？或优先队列方法的任何优化？如果需要，我可以 post 我的两个代码。
谢谢。
一种方法是使用 binary indexed tree 创建一个数据结构，以便在 O(logn) 时间内轻松执行两个操作：
- 将数字插入数组
- 找到给定范围内的最大值
我们将使用此数据结构来保存通过选择框 i 以及左侧框的最佳选择可以获得的最大权重。
关键是我们只会在到达满足正确约束的点时才将值插入此数据结构。
要找到第 i 个框的最佳值，我们需要在数据结构中找到位置 i-left[i] 之前所有点的最大值，这可以在 O(logn) 中完成。
最终算法是遍历 i=0..n-1 并且对于每个 i:
- 通过在范围 0..(i-left[i]) 中找到最大值来计算框 i 的结果
- 调度到达位置i+right[i]时要添加的结果
- 将任何先前计划的结果添加到我们的数据结构中
最后的结果是整个数据结构中的最大值
总体而言，复杂度为 o(nlogn)，因为 i 的每个值都会导致一次查找和一次更新操作。
我最近遇到了一个有趣的编码问题，如下：
有n个盒子，假设这是一个有n个盒子的数组。
对于这个数组的每个索引i，给出三个值-
1.) 体重(i)
2.) 左(i)
3.) 右(i)
left(i) 意思是 - 如果选择了 weight[i]，我们就不能从这个 ith element.
left[i] 个元素
同理，right[i]表示如果选择了arr[i]，则不允许选择其右边的right[i]个元素。
示例：
体重[2] = 5
左[2] = 1
右[2] = 3
然后，如果我在位置 2 选择元素，我得到 5 个单位的权重。但是，我无法在位置 {1} 处选择元素（由于左约束）。并且不能在位置 {3,4,5} 拾取元素（由于右约束）。
Objective - 我们需要计算我们可以选择的权重的最大总和。
示例测试用例：-
**输入：**
5
2 0 3
4 0 0
3 2 0
7 2 1
9 2 0
**输出：**
13
注意 - 第一列是权重，第二列是左约束，第三列是右约束
我使用动态规划方法（类似于最长递增子序列）来得出O(n^2)解。但是，想不出 O(n*logn) 解决方案。 (n can be up to 10^5.)
我也尝试过使用优先级队列，其中(right[i] + i)值较低的元素被赋予较高的优先级（assigned higher priority to element with lower value of "i"，以防主键值相等）。但是，它也给出了超时错误。
还有其他方法吗？或优先队列方法的任何优化？如果需要，我可以 post 我的两个代码。 谢谢。
一种方法是使用 binary indexed tree 创建一个数据结构，以便在 O(logn) 时间内轻松执行两个操作：
- 将数字插入数组
- 找到给定范围内的最大值
我们将使用此数据结构来保存通过选择框 i 以及左侧框的最佳选择可以获得的最大权重。
关键是我们只会在到达满足正确约束的点时才将值插入此数据结构。
要找到第 i 个框的最佳值，我们需要在数据结构中找到位置 i-left[i] 之前所有点的最大值，这可以在 O(logn) 中完成。
最终算法是遍历 i=0..n-1 并且对于每个 i:
- 通过在范围 0..(i-left[i]) 中找到最大值来计算框 i 的结果
- 调度到达位置i+right[i]时要添加的结果
- 将任何先前计划的结果添加到我们的数据结构中
最后的结果是整个数据结构中的最大值
总体而言，复杂度为 o(nlogn)，因为 i 的每个值都会导致一次查找和一次更新操作。