前記

這篇文章的主要內容其實大部分都包含在我三年多前寫的一篇知乎文章所配套的Github中

上個月在知乎上看到一篇寫得很幹貨的相關文章

裡面提到一個括號生成問題（Leetcode problem 22）與隨機矩陣之間的聯系（其實很多問題都可以轉化成括號匹配問題，例如Dyck path，Dyck words，標準Young表（如果是一般的Young tableaux，它與最長遞增子序列存在緊密聯系，這在本文最後部分也有所體現），不相交的弦，出棧序列，筆畫群峰，滿二叉樹等）。這突然使我想到另一個與隨機矩陣理論有關的編程問題，即最長遞增子序列（Longest Increasing Subsequence，LIS，也被稱為最長上升子序列、最長增長子序列等），它對應於Leetcode problem 300。雖然在該文章的相關回答中，我給瞭一些信息，但還是覺得這個題目值得一寫，這便是這篇文章的由來。

最長遞增子序列（LIS）

問題描述：

給定一個無序的整數數組nums，找到其中最長嚴格遞增子序列的長度。

示例1：