最长递增子序列问题c++动态规划

最长递增子序列（Longest Increasing Subsequence，简称LIS）问题是一个经典的计算机科学问题，它被定义为：给定一个序列，找到最长的子序列（可以不连续）使得其中的元素按照顺序递增。

C++中可以使用动态规划算法解决该问题。具体步骤如下：

1. 定义一个数组dp，其中dp[i]表示以第i个元素结尾的最长递增子序列长度。

2. 初始化dp数组，将所有元素的dp值初始化为1。

3. 对于每个元素i，遍历其前面的所有元素j（j<i），如果第j个元素小于第i个元素，那么将dp[i]更新为dp[j]+1。

4. 遍历整个dp数组，找到其中最大的值max，即为最长递增子序列的长度。

5. 可以使用一个辅助数组prev来记录最长递增子序列中每个元素的前一个元素位置，从而还原出最长递增子序列。

以下是C++代码示例：

#include <iostream>
#include <vector>
using namespace std;

int LIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    vector<int> prev(n, -1);
    int max_len = 1;
    int end = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
        }
        if (dp[i] > max_len) {
            max_len = dp[i];
            end = i;
        }
    }
    vector<int> lis;
    while (end != -1) {
        lis.push_back(nums[end]);
        end = prev[end];
    }
    reverse(lis.begin(), lis.end());
    for (int i = 0; i < lis.size(); i++) {
        cout << lis[i] << " ";
    }
    cout << endl;
    return max_len;
}

int main() {
    vector<int> nums = {3, 4, -1, 0, 6, 2, 3};
    int len = LIS(nums);
    cout << len << endl;
    return 0;
}