C++ 最长不降子序列

在C++中，最长不降子序列（Longest Increasing Subsequence, LISP）是一个经典的动态规划问题。它是指在一个序列中找到一个最长的连续递增子序列。例如，对于序列 [10, 9, 2, 5, 3, 7, 101, 18]，最长不降子序列为 [2, 3, 7, 101]，总长度为4。

解决这个问题通常会使用动态规划方法，创建一个数组 `dp` 来存储每个位置的最长不降子序列的长度。算法的核心思想是从左到右遍历序列，对于每个元素，如果当前元素大于前一个元素，则更新其对应的 `dp` 值为其前面元素的 `dp` 值加一；否则，取当前位置元素的 `dp` 值为 `1`，因为单个元素本身就是它的最长不降子序列。

C++代码示例：

#include <vector>
int lengthOfLIS(std::vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return 0;
    std::vector<int> dp(n, 1); // 初始化所有元素为1（单个数都是其子序列）
    for (size_t i = 1; i < n; ++i) {
        for (size_t j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }
    return *std::max_element(dp.begin(), dp.end()); // 返回最长递增子序列的最大值
}