深入解析最大和递增子序列：从递归到动态规划的算法演进

2026-02-03 23:12:48 0条评论 3次阅读 0人点赞

在本篇文章中，我们将深入探讨一种非常经典且具有挑战性的动态规划问题——最大和递增子序列。如果你已经熟悉“最长递增子序列（LIS）”问题，那么你会发现这个问题是它的一个非常有趣的变体。不同于传统的 LIS 问题关注子序列的长度，这里我们将目光聚焦于子序列元素的和。我们将一起从最直观的递归解法出发，逐步过渡到高效的动态规划方案，并探讨其中的优化细节。

问题背景与定义

首先，让我们明确一下问题的具体定义。给定一个由 INLINECODEc97c186f 个正整数组成的数组 INLINECODE567a36c1，我们的目标是找到一个子序列，这个子序列必须满足以下两个条件：

  • 严格递增：子序列中的元素在原数组中的顺序必须保持不变，且数值严格递增。
  • 最大和：在所有满足上述条件的子序列中，我们需要找到元素之和最大的那个。

注意：这是一个子序列问题，不是子数组问题。这意味着我们不需要连续选取元素，可以跳过某些元素来构建我们的序列。

#### 示例解析

为了让你更直观地理解，让我们通过两个具体的例子来看看。

示例 1：

> 输入： arr[] = [1, 101, 2, 3, 100]

>

> 让我们分析一下所有可能的递增子序列及其和：

> * [1, 101] 和为 102

> * [1, 2, 3, 100] 和为 106

> * [1, 2, 100] 和为 103

> * [2, 3, 100] 和为 105

>

> 显然，输出：106。最大的和来源于序列 [1, 2, 3, 100]。注意这里虽然 101 很大，但它阻碍了后面 2, 3, 100 的加入，所以贪心策略并不适用。

示例 2：

> 输入： arr[] = [4, 1, 2, 3]

>

> 在这里，元素 INLINECODE47250f78 是第一个元素，但比它小的元素在后面。包含 INLINECODE2b577c5c 的递增子序列只有 INLINECODEfce47358。如果我们跳过 INLINECODE18c31a78，我们可以得到 [1, 2, 3]。

> * [4] 和为 4

> * [1, 2, 3] 和为 6

>

> 显然，输出：6。

方法一：朴素递归法 – 探索所有可能

作为经验丰富的开发者，我们在面对这类问题时，首先想到的往往是递归。让我们尝试把问题拆解。

#### 思路解析

对于数组中的每一个元素，我们在构建子序列时都面临着两个选择：把它放进当前的子序列 或者 不把它放进子序列。

假设我们使用两个指针来进行递归：

  • i：当前正在考虑的元素索引（从 1 开始）。
  • j：上一个被选入子序列的元素索引（如果还没选，则为 0）。

决策逻辑：

  • 如果 INLINECODEe0a66d8c 为 0（说明这是第一个元素），或者当前元素 INLINECODE06a3317e 大于上一个选中的元素 arr[j-1]：

* 选项 A（包含当前元素）：我们将 INLINECODEe6d1f0b1 加到总和中，并将 INLINECODEb95a5fa3 更新为 i，继续递归。

* 选项 B（不包含当前元素）：我们保持 j 不变，跳过当前元素，递归下一个。

* 我们需要返回这两个选项中结果较大的那个。

  • 如果当前元素 INLINECODE5b8f9c94 小于等于 INLINECODE2403c74c：

* 破坏了递增性质：我们不能选择当前元素，只能跳过它。

这种方法的时间复杂度是指数级的 O(2^n)，因为对于每个元素我们几乎都有两种选择。虽然对于小规模数据（如 n=20）尚可，但在实际工程中这通常会导致 Time Limit Exceeded（TLE）。

#### 代码实现

让我们把上述逻辑转化为代码。这里我们使用 C++、Java、Python 和 C# 来展示。

C++ 实现

#include 
#include 
#include 
using namespace std;

// 递归辅助函数
// i: 当前考虑的元素索引 (1-based)
// j: 上一个被选中元素的索引 (1-based, 0表示尚未选中)
int findMaxSum(vector& arr, int i, int j) {
    int n = arr.size();
    // 基本情况：如果索引越界，返回0
    if (i == n + 1) return 0;
    
    // 如果这是第一个元素，或者满足严格递增条件
    if (j == 0 || arr[i-1] > arr[j-1]) {
        // 选择1：包含当前元素 arr[i-1]，总和增加，上一选中索引变为 i
        int include = arr[i-1] + findMaxSum(arr, i + 1, i);
        // 选择2：不包含当前元素，继续寻找
        int exclude = findMaxSum(arr, i + 1, j);
        
        return max(include, exclude);
    } 
    else {
        // 当前元素不大于上一元素，无法包含，只能跳过
        return findMaxSum(arr, i + 1, j);
    }
}

int maxSumIS(vector& arr) {
    return findMaxSum(arr, 1, 0);
}

int main() {
    vector arr = {1, 101, 2, 3, 100};
    cout << "最大和递增子序列: " << maxSumIS(arr) << endl;
    return 0;
}

Java 实现

class MaxSumSubsequence {

    static int findMaxSum(int[] arr, int i, int j) {
        // 基本情况：所有元素已处理完毕
        if (i == arr.length + 1) return 0;
        
        // j == 0 代表还没有选取任何元素作为“前驱”
        // arr[i-1] > arr[j-1] 确保子序列是严格递增的
        if (j == 0 || arr[i-1] > arr[j-1]) {
            // 路径1：选中当前元素，更新 j 为 i，累加当前值
            int take = arr[i-1] + findMaxSum(arr, i + 1, i);
            // 路径2：跳过当前元素
            int skip = findMaxSum(arr, i + 1, j);
            
            return Math.max(take, skip);
        } else {
            // 不满足递增条件，只能跳过
            return findMaxSum(arr, i + 1, j);
        }
    }

    static int maxSumIS(int[] arr) {
        return findMaxSum(arr, 1, 0);
    }

    public static void main(String[] args) {
        int[] arr = {1, 101, 2, 3, 100};
        System.out.println("最大和递增子序列: " + maxSumIS(arr));
    }
}

Python 实现

def findMaxSum(arr, i, j):
    # 递归终止条件：索引越界
    if i == len(arr) + 1:
        return 0
    
    # j == 0 表示刚开始，或者当前元素大于上一个选中的元素
    if j == 0 or arr[i - 1] > arr[j - 1]:
        # 情况1：选中 arr[i-1]
        included = arr[i - 1] + findMaxSum(arr, i + 1, i)
        # 情况2：不选中 arr[i-1]
        excluded = findMaxSum(arr, i + 1, j)
        
        return max(included, excluded)
    else:
        # 不满足递增，只能跳过
        return findMaxSum(arr, i + 1, j)

def maxSumIS(arr):
    return findMaxSum(arr, 1, 0)

if __name__ == "__main__":
    arr = [1, 101, 2, 3, 100]
    print(f"最大和递增子序列: {maxSumIS(arr)}")

C# 实现

using System;

class MaxSumIS {
    static int findMaxSum(int[] arr, int i, int j) {
        int n = arr.Length;
        if (i == n + 1) return 0;
        
        // 如果是第一个元素，或者当前元素大于上一个选中元素
        if (j == 0 || arr[i-1] > arr[j-1]) {
            // 取 max(选中当前, 跳过当前)
            return Math.Max(arr[i-1] + findMaxSum(arr, i+1, i), 
                            findMaxSum(arr, i+1, j));
        } else {
            return findMaxSum(arr, i+1, j);
        }
    }
    
    static int maxSumIS(int[] arr) {
        return findMaxSum(arr, 1, 0);
    }

    static void Main() {
        int[] arr = {1, 101, 2, 3, 100};
        Console.WriteLine("最大和递增子序列: " + maxSumIS(arr));
    }
}

方法二：带记忆化的递归（自顶向下 DP）

如果你运行上面的代码，你会发现对于稍微大一点的数组（比如长度超过 30），程序会变得非常慢。这是因为我们重复计算了大量的状态。比如，在决策是否选第 5 个元素时，可能会遇到“前一个元素是第 3 个”的情况，而在另一条递归路径中也会遇到这种情况。

优化思路：使用一个二维数组 INLINECODEd01b9254 来存储状态 INLINECODEe4a80708 对应的结果。一旦计算过，就直接读取，不再递归。

这把时间复杂度降低到了 O(n^2)，因为我们只计算 n*n 种状态。空间复杂度主要取决于递归栈深度和 memo 数组的大小，即 O(n^2)。

#### C++ 记忆化示例

#include 
#include 
#include 
#include  // for memset
using namespace std;

// 全局 Memo 表，初始化为 -1 表示未访问
int dp[1005][1005]; 

int findMaxSum(vector& arr, int i, int j) {
    if (i == arr.size() + 1) return 0;
    
    // 如果该状态已计算，直接返回
    if (dp[i][j] != -1) return dp[i][j];
    
    int res;
    if (j == 0 || arr[i-1] > arr[j-1]) {
        res = max(arr[i-1] + findMaxSum(arr, i+1, i), 
                  findMaxSum(arr, i+1, j));
    } else {
        res = findMaxSum(arr, i+1, j);
    }
    
    // 存入 Memo 表
    return dp[i][j] = res;
}

int maxSumIS(vector& arr) {
    // 初始化 Memo 表
    memset(dp, -1, sizeof(dp)); 
    return findMaxSum(arr, 1, 0);
}

int main() {
    vector arr = {1, 101, 2, 3, 100};
    cout << "最大和: " << maxSumIS(arr) << endl;
    return 0;
}

方法三：自底向上动态规划 – O(n) 空间优化

虽然自顶向下的方法不错，但在实际工程中，我们往往更喜欢迭代的写法，因为它避免了递归带来的栈溢出风险，且通常常数因子更小。

我们可以定义一个一维数组 INLINECODE9a80662c，其中 INLINECODE8be0f47f 表示必须以 arr[i] 结尾的最大和递增子序列的和。

算法逻辑：

  • 初始化：对于任何单个元素，至少它自己就是一个序列，所以 msis[i] = arr[i]。
  • 遍历：对于每个 INLINECODE1f4142a4 (从 0 到 n-1)，我们检查它之前的所有元素 INLINECODE540f7c60 (从 0 到 i-1)。
  • 转移：如果 INLINECODE72ec52c0，说明我们可以把 INLINECODE91e6f185 接在 INLINECODE710b05ca 后面。此时，以 INLINECODE14c387fb 结尾的最大和可能是 INLINECODE13065176。我们遍历所有合法的 INLINECODEa1e9b6e0，取最大值更新 msis[i]。
  • 结果：最终数组的最大值就是答案，因为最大和序列可能以任意下标结尾。

这种方法的时间复杂度是 O(n^2)（两层循环），空间复杂度优化到了 O(n)。

#### 代码实现

int maxSumIS(vector& arr) {
    int n = arr.size();
    if (n == 0) return 0;
    
    // dp[i] 保存以 arr[i] 为结尾的最大和
    vector dp(n);
    
    // 初始状态：每个元素自身构成一个序列
    for(int i = 0; i < n; i++) {
        dp[i] = arr[i];
    }
    
    // 动态规划填表
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // 如果 arr[j] < arr[i]，说明可以接上
            if (arr[j] < arr[i]) {
                dp[i] = max(dp[i], dp[j] + arr[i]);
            }
        }
    }
    
    // 结果是 dp 数组中的最大值
    return *max_element(dp.begin(), dp.end());
}

实际应用与常见陷阱

在实际开发面试或应用中，以下几个点值得你特别注意：

  • 严格递增 vs 非严格递增：题目要求的是“严格递增”，所以判断条件只能用 INLINECODEec7bc8dc 或 INLINECODEcd89fd05。如果是“非严格递增”，则需要改为 INLINECODE38e50029 或 INLINECODE684c6fd8。这往往是一个容易出错的细节。
  • 初始值的设定：在自底向上的方法中，不要忘记 INLINECODEf092634f 的初始值必须是 INLINECODE96aaf1bd。如果你初始化为 0，当数组中全是负数时（虽然本题说是正整数，但在变种中可能遇到），你的逻辑就会出错，因为任何负数都比 0 小，但实际上取负数才是合法的。
  • 空间换时间：虽然上述 DP 已经是标准解法，但如果数据规模极大（n > 10^5），O(n^2) 可能会不够用。这时候可能需要结合更高级的数据结构（如线段树或 Fenwick Tree）来优化查找过程，可以将复杂度降至 O(n log n)，但实现难度会显著增加。

总结

我们从最朴素的递归思路出发，识别出重叠子问题，进而引入了记忆化搜索和动态规划。对于最大和递增子序列问题，掌握 O(n^2) 的动态规划解法是基础中的基础。理解 INLINECODE3451e4f3 的定义（以 INLINECODEd39974aa 结尾）以及状态转移方程，将帮助你举一反三地解决类似的最长递增子序列（LIS）或最大乘积递增子序列问题。

希望这篇文章能帮助你彻底搞懂这个算法！如果你在练习中遇到了困难，不妨试着在纸上画出递归树，或者手动模拟一遍 DP 数组的变化，这往往比盯着代码看更有效果。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/23394.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年