c++求最长单调递增子序列长度

在 C++ 中，求解给定数组的最长单调递增子序列（Longest Increasing Subsequence，LIS）通常采用动态规划的方法。一种常见的算法是“Kadane's Algorithm”或称为“一次遍历法”。以下是基本步骤：

1. 初始化一个大小与输入数组相同的数组 `dp`，所有元素初始化为1。因为每个数本身都是一个长度为1的单调递增子序列。

2. 遍历输入数组 `nums`，对于每个数 `nums[i]`，比较它与 `dp[j] (j < i)` 的值。如果 `nums[i] > dp[j]`，则将 `dp[i]` 更新为 `dp[j] + 1`，这意味着找到了一个新的更长的递增子序列。

3. 在遍历过程中，同时维护一个变量 `max_len`，记录已经找到的最大单调递增子序列长度。这个变量会在每次更新 `dp[i]` 后进行检查。

4. 遍历结束后，`dp[nums.size() - 1]` 就是最长递增子序列的长度。

下面是简单的 C++ 代码实现：

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    int max_len = 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);
                max_len = max(max_len, dp[i]);
            }
        }
    }
    return max_len;
}