最长递增子序列

最长递增子序列(Longest Increasing Subsequence, LIS)是动态规划中的经典问题，在众多应用场景中有重要意义。

问题定义

【定义】给定一个数字序列，找出其中最长的严格递增子序列的长度。子序列是从原序列中删除零个或多个元素后得到的序列，保持剩余元素的相对顺序不变。

例如：

• 序列[10, 9, 2, 5, 3, 7, 101, 18]的最长递增子序列是[2, 3, 7, 18]或[2, 3, 7, 101]，长度为4。

动态规划解法

方法一：基本DP解法（O(n²)）

状态定义

设dp[i]表示以第i个元素结尾的最长递增子序列的长度。

状态转移方程

对于每个位置i，我们需要找出所有满足j < i且nums[j] < nums[i]的位置j，取其中dp[j]的最大值，然后加1：

dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i]

如果不存在这样的j，则dp[i] = 1（只包含元素自身）。

代码实现

// 使用DP求最长递增子序列，O(n²)算法
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    // dp[i]表示以nums[i]结尾的最长递增子序列的长度
    vector<int> dp(n, 1);  // 初始化为1，因为单个元素也是递增子序列

    int maxLength = 1;  // 记录最长长度

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        maxLength = max(maxLength, dp[i]);
    }

    return maxLength;
}

方法二：二分查找优化（O(n log n)）

方法一的时间复杂度为O(n²)，在处理大规模数据时效率不高。我们可以使用二分查找来优化。

算法思想

维护一个数组tails，其中tails[i]表示长度为i+1的递增子序列的末尾元素的最小值。

对于每个元素x，我们可以在tails数组中使用二分查找，找到tails中第一个大于等于x的位置，并更新该位置的值为x。

代码实现

// 使用二分查找优化的最长递增子序列，O(n log n)算法
int lengthOfLIS_optimized(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;

    // tails[i]表示长度为i+1的递增子序列的末尾元素的最小值
    vector<int> tails(n, 0);
    int len = 0;  // 当前找到的最长递增子序列的长度

    for (int num : nums) {
        // 在tails中二分查找第一个大于等于num的位置
        int left = 0, right = len;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 更新tails数组
        tails[left] = num;

        // 如果我们在当前的末尾添加一个新元素，则增加长度
        if (left == len) {
            len++;
        }
    }

    return len;
}

输出最长递增子序列

除了求解LIS的长度外，有时还需要输出具体的最长递增子序列。

方法一：基于基本DP解法输出

// 输出最长递增子序列
vector<int> findLIS(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {};

    vector<int> dp(n, 1);  // dp[i]表示以nums[i]结尾的LIS长度
    vector<int> prev(n, -1);  // prev[i]表示LIS中nums[i]的前一个元素的索引

    int maxLength = 1;
    int endIndex = 0;  // 最长子序列的结束索引

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                prev[i] = j;  // 记录前一个元素的索引
            }
        }

        // 更新最长长度和结束索引
        if (dp[i] > maxLength) {
            maxLength = dp[i];
            endIndex = i;
        }
    }

    // 回溯构建LIS
    vector<int> lis;
    while (endIndex != -1) {
        lis.push_back(nums[endIndex]);
        endIndex = prev[endIndex];
    }

    // 逆序得到正确的LIS
    reverse(lis.begin(), lis.end());
    return lis;
}

方法二：基于二分查找解法输出

使用二分查找优化的方法也可以输出LIS，但需要额外的记录：

// 使用二分查找并输出最长递增子序列
vector<int> findLIS_optimized(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return {};

    vector<int> tails(n, 0);  // tails[i]表示长度为i+1的LIS的末尾最小值
    vector<int> indices(n, 0);  // indices[i]表示长度为i+1的LIS的末尾元素在nums中的索引
    vector<int> prev(n, -1);  // prev[i]表示nums[i]前一个元素在LIS中的索引

    int len = 0;  // 当前LIS长度

    for (int i = 0; i < n; i++) {
        int left = 0, right = len;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (tails[mid] < nums[i]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        // 如果当前位置前有元素，记录前驱
        if (left > 0) {
            prev[i] = indices[left - 1];
        }

        tails[left] = nums[i];
        indices[left] = i;

        if (left == len) {
            len++;
        }
    }

    // 回溯构建LIS
    vector<int> lis;
    int index = indices[len - 1];
    while (index != -1) {
        lis.push_back(nums[index]);
        index = prev[index];
    }

    reverse(lis.begin(), lis.end());
    return lis;
}

变种问题

最长递减子序列 (LDS)

只需将原序列取负或反向比较即可转化为LIS问题。

// 最长递减子序列
int lengthOfLDS(vector<int>& nums) {
    vector<int> reversed(nums);
    for (int& num : reversed) {
        num = -num;  // 取负转换为LIS问题
    }
    return lengthOfLIS(reversed);
}

最长不降子序列（可以包含相等元素）

只需修改比较条件：

// 最长不降子序列
int lengthOfLNDS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] >= nums[j]) {  // 允许相等
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

最长交替子序列（最长摆动子序列）

找出序列中最长的子序列，使得子序列中相邻元素的差交替出现正负。

// 最长交替子序列
int lengthOfLAS(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return n;

    // dp[i][0]表示以nums[i]结尾且最后一个差为负的最长交替子序列长度
    // dp[i][1]表示以nums[i]结尾且最后一个差为正的最长交替子序列长度
    vector<vector<int>> dp(n, vector<int>(2, 1));

    int result = 1;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                // 当前差为正，前一个差应为负
                dp[i][1] = max(dp[i][1], dp[j][0] + 1);
            } else if (nums[i] < nums[j]) {
                // 当前差为负，前一个差应为正
                dp[i][0] = max(dp[i][0], dp[j][1] + 1);
            }
        }
        result = max({result, dp[i][0], dp[i][1]});
    }

    return result;
}

二维LIS（信封问题）

给定一组信封的宽度和高度，一个信封可以放入另一个信封当且仅当它的宽度和高度都小于另一个信封。求最多可以嵌套的信封数量。

// 信封嵌套问题
int maxEnvelopes(vector<vector<int>>& envelopes) {
    // 按宽度升序排序，宽度相同时按高度降序排序
    sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
    });

    // 在高度上应用LIS算法
    vector<int> heights;
    for (auto& env : envelopes) {
        heights.push_back(env[1]);
    }

    return lengthOfLIS_optimized(heights);
}

时间和空间复杂度

• 基本DP算法

  • 时间复杂度：O(n²)
  • 空间复杂度：O(n)

• 二分查找优化

  • 时间复杂度：O(n log n)
  • 空间复杂度：O(n)

实战技巧

1. 识别问题类型：许多看似不相关的问题可以转化为LIS问题
2. 使用二分查找优化：当处理大规模数据时，二分查找优化至关重要
3. 灵活变形：根据问题需求灵活调整比较条件（如不降序、交替等）
4. 多维情况：对于多维问题，可先排序然后在一个维度上应用LIS

实际应用

1. 序列分析：在金融数据、基因序列等领域分析趋势
2. 塔堆叠问题：物体按特定条件堆叠的最大高度
3. 网络包分析：分析网络流中的有序事件
4. 游戏设计：解决策略游戏中的升级路径问题

练习题目推荐

1. LeetCode 300: Longest Increasing Subsequence (经典LIS问题)
2. LeetCode 354: Russian Doll Envelopes (二维LIS问题)
3. LeetCode 673: Number of Longest Increasing Subsequence (计算LIS数量)
4. LeetCode 1048: Longest String Chain (字符串链的LIS变种)
5. LeetCode 674: Longest Continuous Increasing Subsequence (连续递增子序列)
6. POJ 2533: Longest Ordered Subsequence (基础LIS练习)

总结

最长递增子序列问题是动态规划中的经典问题，通过本章的学习，你应该:

1. 理解LIS问题的基本定义和解法
2. 掌握O(n²)动态规划解法和O(n log n)二分查找优化方法
3. 能够解决LIS的各种变种问题
4. 学会将其他问题转化为LIS问题来解决
5. 熟练掌握LIS问题在实际应用中的常见技巧

通过不断练习和应用，你将能够灵活运用LIS算法解决更复杂的实际问题。