《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（32）万剑归宗破妖阵 - 最长递增子序列（LIS）

《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（32）万剑归宗破妖阵 - 最长递增子序列（LIS）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的万剑谷，谷中有一座巨大的万剑归宗剑阵，剑阵闪烁着神秘的光芒。谷口有一块巨大的石碑，上面刻着一行文字：“欲破此阵，需以万剑归宗之力，破妖阵，最长递增子序列显真身。”

哪吒定睛一看，石碑上还有一行小字：“数组[10, 9, 2, 5, 3, 7, 101, 18]的最长递增子序列为[2, 5, 7, 101]，长度为4。”哪吒心中一动，他知道这是一道关于寻找最长递增子序列（LIS）的难题，需要通过动态规划或二分优化的方法，找到数组中最长的递增子序列。

暴力解法：万剑归宗的初次尝试

哪吒心想：“要寻找最长递增子序列，我可以逐个元素比较。”他催动万剑归宗之力，从数组的第一个元素开始，逐个元素比较，试图找到最长的递增子序列。

int lengthOfLIS(vector<int>& nums) {
   
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i]表示以nums[i]结尾的最长递增子序列的长度
    for (int i = 0; i < n; ++i) {
   
        for (int j = 0; j < i; ++j) {
   
            if (nums[i] > nums[j]) {
   
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

哪吒成功地找到了最长递增子序列，但万剑归宗的光芒却黯淡了下来。他意识到，这种方法虽然可行，但效率低下，尤其是当数组很大时，灵力消耗巨大。

C++语法点

在C++中，动态规划是解决最长递增子序列问题的常用方法。以下是一些重要特性：

• 动态规划：

  • 动态规划通过将问题分解为子问题，并存储子问题的解来避免重复计算。
  • 常用操作：
    • 使用vector动态数组存储子问题的解。
    • 通过状态转移方程计算当前问题的解。

• 数组操作：

  • 使用vector<int>表示动态数组。
  • 常用方法：
    • vector<int> dp(n, 1)：创建一个大小为n的动态数组，并初始化所有元素为1。
    • max_element(dp.begin(), dp.end())：找到数组中的最大值。

高阶优化：二分优化的智慧

哪吒元神中突然浮现金色铭文——「万剑归宗，二分优化显真身」。他意识到，可以通过二分优化的方法，将时间复杂度降低到O(n log n)。

哪吒决定使用二分优化，维护一个数组tails，其中tails[i]表示长度为i+1的递增子序列的最小末尾元素。通过这种方式，他成功地找到了最长递增子序列，而且灵力消耗大幅减少。

int lengthOfLIS(vector<int>& nums) {
   
    vector<int> tails;
    for (int num : nums)