最长递增子序列c++递推公式

最长递增子序列（Longest Increasing Subsequence，LIS）是指在一个无序的序列中，找到一个尽可能长的子序列，使得这个子序列中的元素是递增的。下面是C++的递推公式：

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

其中，`dp[i]`表示以`nums[i]`为结尾的最长递增子序列的长度。在遍历`nums`数组时，对于每个`i`，都需要遍历`0~i-1`的所有元素，如果`nums[i]`大于`nums[j]`，则可以将`dp[i]`更新为`dp[j]+1`，表示在以`nums[j]`为结尾的最长递增子序列后面加上`nums[i]`可以得到一个更长的递增子序列。最后，遍历`dp`数组，找到其中的最大值即为所求的最长递增子序列的长度。