最长数对链的变种：带权值的最长数对链

题目描述

给定一个由数对组成的数组pairs，其中每个数对pairs[i] = [left_i, right_i]，且left_i < right_i。我们定义数对链为一系列数对，其中每个数对的right_i严格小于下一个数对的left_j。

与标准的最长数对链问题不同，每个数对现在有一个权值weight_i。我们需要找到权值和最大的数对链（注意：不是链的长度最长，而是权值和最大）。

示例

输入: pairs = [[1,2,10], [2,3,20], [3,4,30]]
输出: 60
解释: 最长数对链是 [1,2,10] → [2,3,20] → [3,4,30]，权值和为10+20+30=60

解题过程

步骤1：问题分析
这是一个带权值的区间调度问题。我们需要选择一组不重叠的区间（数对），使得它们的权值和最大。这类似于带权区间调度问题，但每个区间的权值可能不同。

步骤2：动态规划状态定义
定义dp[i]为以第i个数对结尾的最大权值数对链的权值和。

步骤3：状态转移方程
对于每个数对i，我们需要找到所有可以放在它前面的数对j（即pairs[j][1] < pairs[i][0]），然后：

dp[i] = max(dp[j] for j in range(i) if pairs[j][1] < pairs[i][0]) + weight_i

如果找不到这样的j，那么dp[i] = weight_i（即数对i自己构成一个链）。

步骤4：预处理排序
为了确保状态转移的正确性，我们需要按照数对的右端点进行排序。这样在寻找可以接在当前数对前面的数对时，可以使用二分查找优化。

步骤5：算法实现细节

1. 对pairs按照right_i进行排序
2. 初始化dp数组，dp[i]表示以第i个数对结尾的最大权值和
3. 对于每个数对i，使用二分查找找到所有右端点小于left_i的数对
4. 取这些数对中dp值的最大值，加上当前数对的权值

步骤6：优化
使用二分查找可以将寻找前驱的时间复杂度从O(n)降到O(log n)，总体时间复杂度为O(n log n)。

步骤7：最终答案
最终的答案是所有dp[i]中的最大值，因为最长数对链不一定以最后一个数对结尾。

完整算法步骤：

1. 对pairs按照right_i排序
2. 初始化dp数组和rights数组（记录已处理数对的右端点）
3. 遍历每个数对：
   • 使用二分查找在rights数组中找到最后一个右端点小于当前left_i的位置
   • 如果找到，dp[i] = dp[pos] + weight_i
   • 否则，dp[i] = weight_i
   • 维护dp[i] = max(dp[i], dp[i-1])（可选优化）
4. 返回dp数组中的最大值

这个算法的时间复杂度是O(n log n)，空间复杂度是O(n)。