带权最大不下降子序列（Maximum Sum Non-decreasing Subsequence）

题目描述

给定一个整数数组 nums，你需要找到一个不下降子序列（子序列中相邻元素满足 nums[i] <= nums[i+1]），使得这个子序列的权重和最大。每个元素 nums[i] 有一个对应的正权重 weights[i]。你需要返回最大权重和。

例如：

nums = [1, 3, 2, 4, 5]
weights = [1, 2, 5, 3, 2]

一个不下降子序列是 [1, 3, 4, 5]，权重和为 1 + 2 + 3 + 2 = 8。但最优解是 [1, 2, 4, 5]，权重和为 1 + 5 + 3 + 2 = 11（因为权重 5 很大）。注意子序列不一定连续，但必须保持原数组顺序，且相邻元素不下降。

解题过程

这个问题是经典最长不下降子序列（LNDS）的带权值变种。在 LNDS 中，我们通常定义 dp[i] 为以第 i 个元素结尾的最长不下降子序列长度。这里我们要求最大权重和，所以将状态定义调整为：

dp[i] 表示以第 i 个元素结尾的、满足不下降条件的最大权重和。

转移方程思考：
对于位置 i，我们需要检查所有在 i 之前的元素 j（0 <= j < i）。如果 nums[j] <= nums[i]，那么 nums[i] 可以接在以 nums[j] 结尾的不下降子序列后面，形成一个以 i 结尾的新序列，其权重和为 dp[j] + weights[i]。我们需要取所有可能中的最大值。
同时，还有一种情况是子序列只包含 nums[i] 自己，其权重和为 weights[i]。
因此：

\[dp[i] = \max\left(weights[i],\ \max_{j < i,\ nums[j] \le nums[i]} (dp[j] + weights[i]) \right) \]

最终答案是所有 dp[i] 中的最大值。

逐步推导示例

用上面的例子：

nums  = [1, 3, 2, 4, 5]
weights = [1, 2, 5, 3, 2]

初始化 dp 数组长度 5，先全部设为对应权重（表示只取自己的情况）：

dp[0] = weights[0] = 1
dp[1] = weights[1] = 2
dp[2] = weights[2] = 5
dp[3] = weights[3] = 3
dp[4] = weights[4] = 2

计算过程：

• i = 0：前面没有元素，dp[0] 保持 1。
• i = 1：检查 j = 0，因为 nums[0]=1 <= nums[1]=3，可以接，dp[0] + weights[1] = 1+2=3，比当前 dp[1]=2 大，所以更新 dp[1] = 3。
• i = 2：检查前面的 j：
  • j=0：1 <= 2 成立，dp[0]+weights[2] = 1+5=6，比当前 5 大，暂存 6。
  • j=1：3 > 2 不成立，跳过。
    取最大值，dp[2] = max(5, 6) = 6。
• i = 3：
  • j=0：1 <= 4，1+3=4。
  • j=1：3 <= 4，3+3=6。
  • j=2：2 <= 4，6+3=9。
    最大值是 9，dp[3] = 9。
• i = 4：
  • j=0：1 <= 5，1+2=3。
  • j=1：3 <= 5，3+2=5。
  • j=2：2 <= 5，6+2=8。
  • j=3：4 <= 5，9+2=11。
    最大值是 11，dp[4] = 11。

最终 dp = [1, 3, 6, 9, 11]，最大值是 11，对应子序列是 [1, 2, 4, 5]（权重 1+5+3+2=11）。

时间复杂度优化思考

上述算法时间复杂度为 O(n²)，在 n 很大时可能较慢。有没有优化方法？

对于经典最长不下降子序列问题，我们可以用二分查找 + 维护尾部最小值的数组将复杂度降至 O(n log n)，但那是针对长度的优化。对于带权的情况，因为权重不单调，直接套用二分法不可行。不过，如果权重是正数，那么更长的子序列通常权和更大，但仍需考虑权重差异。一种优化思路是：将 nums 的值离散化，用树状数组（Fenwick Tree）或线段树来维护以某个值结尾的最大权重和，在遍历时，对于当前 nums[i]，查询所有小于等于 nums[i] 的值中的最大 dp 值，再加上 weights[i] 更新。这样可以将复杂度降到 O(n log n)，但需额外空间。下面简述这种优化方法：

1. 将 nums 去重排序，得到值到索引的映射（离散化）。
2. 初始化树状数组 bit，长度等于不同值的个数，bit[x] 表示以值 x 结尾的最大权重和（在遍历过程中更新）。
3. 遍历 i 从 0 到 n-1：
   • 找到 nums[i] 在离散化数组中的位置 pos（从1开始计数）。
   • 查询 bit 中 [1, pos] 区间的最大值 maxSum（即所有值小于等于 nums[i] 的最大 dp 值）。
   • 计算 dp[i] = max(weights[i], maxSum + weights[i])。
   • 更新 bit[pos] 为 max(bit[pos], dp[i])。
4. 最终答案为所有 dp[i] 的最大值。

这样每次查询和更新都是 O(log n)，整体 O(n log n)。

代码框架（朴素 O(n²) 版，易于理解）

def max_weight_non_decreasing_subseq(nums, weights):
    n = len(nums)
    dp = weights[:]  # 初始化为只取自己
    for i in range(n):
        for j in range(i):
            if nums[j] <= nums[i]:
                dp[i] = max(dp[i], dp[j] + weights[i])
    return max(dp)

为什么这是线性动态规划？

• 状态定义是线性的：dp[i] 只与下标 i 相关。
• 转移是从前面的状态线性扫描而来，无后效性（前面的选择不影响后面，只要满足不下降条件）。
• 尽管朴素解法是 O(n²)，但它仍然属于线性 DP 的范畴，因为状态是一维的，只是转移需要遍历前面所有状态。

总结

• 这个题目是带权最长不下降子序列问题，是 LIS 变种中常见的一种。
• 核心状态定义：dp[i] 是以 i 结尾的最大权重和。
• 转移时需检查所有前面的元素能否接在后面（值不下降）。
• 可用数据结构优化到 O(n log n)，但需注意权重为正时，贪心选择不一定最优，仍需动态规划保证正确性。

通过这个例子，你可以理解如何将经典 LIS 问题扩展为带权版本，并掌握其动态规划的解法与优化思路。