《靈珠覺醒：從零到算法金仙的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)