最长上升子序列问题c++

最长上升子序列（Longest Increasing Subsequence, LIS）问题是一个经典的动态规划问题，在C++中通常通过递归或自底向上的迭代算法解决。以下是基本的迭代版本的解法：

#include <vector>
using namespace std;

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> tails(nums.size(), 0);
    int maxLen = 1; // 初始化最长上升子序列长度为1

    for (size_t i = 0; i < nums.size(); ++i) {
        // 查找比当前元素小的所有已知最长上升子序列的尾部元素索引
        int index = lower_bound(tails.begin(), tails.end(), nums[i]) - tails.begin();

        // 如果找到，说明可以将当前元素追加到这个子序列上
        if (index != 0 && tails[index - 1] == nums[i]) {
            tails[index] = tails[index - 1] + 1;
        } else {
            tails[index] = nums[i]; // 否则，创建一个新的子序列，长度为1
        }

        // 更新最大值
        maxLen = max(maxLen, tails[index]);
    }
    return maxLen;
}

在这个算法中，`tails` 数组存储了每个位置之前能构成最长上升子序列的最大长度。对于每个新元素，我们查找其应该插入的位置，并更新相应长度。