最长递增子序列的变种：带权值的最长递增子序列（Maximum Sum Increasing Subsequence）

我将为您详细讲解"带权值的最长递增子序列"问题。这是一个经典的线性动态规划变种，在标准最长递增子序列问题的基础上增加了权值的概念。

问题描述

给定一个整数数组nums和一个权值数组values（长度相同），找到nums的一个严格递增子序列，使得该子序列中对应位置的权值之和最大。

示例：

nums = [1, 3, 2, 4]
values = [10, 20, 15, 30]

最长递增子序列有：[1,3,4]（权值和=60）、[1,2,4]（权值和=55）
最大权值和为60

解题思路

这个问题在标准LIS问题的基础上，将"长度"替换为"权值和"，需要重新定义状态和状态转移方程。

详细解题步骤

步骤1：定义状态

定义dp[i]为以第i个元素结尾的递增子序列的最大权值和。

对于示例：

• dp[0]：以nums[0]=1结尾的最大权值和子序列就是[1]，权值和=10
• dp[1]：以nums[1]=3结尾，可以接在nums[0]=1后面，权值和=10+20=30
• dp[2]：以nums[2]=2结尾，可以接在nums[0]=1后面，权值和=10+15=25
• dp[3]：以nums[3]=4结尾，可以接在nums[0]、nums[1]、nums[2]后面

步骤2：状态转移方程

对于每个位置i，我们需要检查所有j < i：

• 如果nums[j] < nums[i]（满足递增条件）
• 那么dp[i] = max(dp[i], dp[j] + values[i])

同时，每个元素本身可以构成一个长度为1的递增子序列，所以：
dp[i]的初始值为values[i]

状态转移方程：

dp[i] = max(values[i], max_{j=0 to i-1} (dp[j] + values[i]) if nums[j] < nums[i])

步骤3：初始化

dp数组初始化为values数组的拷贝，因为每个元素自身就是一个递增子序列。

步骤4：计算顺序

从左到右计算dp数组，因为计算dp[i]需要用到前面所有dp[j]（j < i）的值。

步骤5：最终结果

最终结果是dp数组中的最大值，因为最大权值和可能以任意元素结尾。

完整示例演示

让我们用完整的例子来演示：

输入：

nums = [1, 3, 2, 4, 5]
values = [10, 20, 15, 30, 25]

逐步计算：

1. i = 0（元素1，权值10）

   • 前面没有元素
   • dp[0] = values[0] = 10

2. i = 1（元素3，权值20）

   • 检查j=0：nums[0]=1 < 3，可以接在后面
   • dp[1] = max(values[1], dp[0] + values[1]) = max(20, 10+20) = 30

3. i = 2（元素2，权值15）

   • 检查j=0：nums[0]=1 < 2，可以接在后面
   • 检查j=1：nums[1]=3 > 2，不能接在后面
   • dp[2] = max(values[2], dp[0] + values[2]) = max(15, 10+15) = 25

4. i = 3（元素4，权值30）

   • 检查j=0：nums[0]=1 < 4，权值和=10+30=40
   • 检查j=1：nums[1]=3 < 4，权值和=30+30=60
   • 检查j=2：nums[2]=2 < 4，权值和=25+30=55
   • dp[3] = max(values[3], 40, 60, 55) = 60

5. i = 4（元素5，权值25）

   • 检查所有前面元素：都可以接在后面
   • 从j=3接：权值和最大=60+25=85
   • dp[4] = 85

最终结果： max(10, 30, 25, 60, 85) = 85

对应的递增子序列是：[1, 3, 4, 5]，权值和=10+20+30+25=85

算法实现

def maximum_sum_increasing_subsequence(nums, values):
    n = len(nums)
    if n == 0:
        return 0
    
    dp = values[:]  # 初始化，每个元素自身构成子序列
    
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + values[i])
    
    return max(dp)

时间复杂度分析

• 时间复杂度： O(n²)，需要两层循环
• 空间复杂度： O(n)，只需要一个dp数组

算法优化

对于标准的最长递增子序列问题，有O(n log n)的优化方法，但对于带权值的版本，由于权值的不规则性，通常难以达到O(n log n)的时间复杂度。不过在某些特殊情况下（如权值与数值相关），可能可以优化。

实际应用

这个算法在以下场景中有重要应用：

1. 股票投资组合优化：选择价格递增的股票，使得总收益最大
2. 任务调度：选择开始时间递增且总价值最大的任务序列
3. 资源分配：在时间序列上选择最优的资源分配方案

这个问题的关键在于理解：虽然我们关注递增性，但优化的目标是权值和而非序列长度，这需要在状态转移时做出相应的调整。