求最长递增子序列C++代码

以下是一种常规的动态规划解法：

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

vector<int> LIS(const vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    vector<int> pre(n, -1);

    int max_len = 1, max_idx = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }
        if (dp[i] > max_len) {
            max_len = dp[i];
            max_idx = i;
        }
    }

    vector<int> res;
    while (max_idx != -1) {
        res.push_back(nums[max_idx]);
        max_idx = pre[max_idx];
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    vector<int> nums = {1, 5, 3, 4, 6, 9, 7, 8};
    vector<int> res = LIS(nums);
    cout << "The longest increasing subsequence is: ";
    for (int num : res) {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}

输入为一个整数数组，返回的是最长递增子序列。具体的思路就是利用动态规划，维护一个状态数组 `dp`，表示以当前位置为结尾的最长递增子序列的长度。同时，再用一个记录数组 `pre`，记录每个状态的前驱位置，方便回溯。最后，通过遍历整个数组找到最大值即可。