主題
題目連結：
題目大意：
第一列給定一正整數，代表有幾組測試資料。每組測資第一列給定一正整數 ｎ （０ ≦ ｎ ≦ ２, ０００），代表有 ｎ 節車廂。
接下來有 ｎ 列輸入，每列給定一非負整數，代表其中一節車廂的重量（每節車廂重量均不同）。
當每有一節車廂抵達車站（以輸入的順序），艾琳可以把它接在現有列車的前方或後方，或是乾脆不要接上列車。使得列車的每節車廂依重量排列。請問，列車最長可以有幾節車廂。
範例輸入：
1
3
1
2
3
範例輸出：
3
解題思維：
本題即是求最長遞增子序列（Longest Increasing Subsequence，LIS），例：5 7 2 3 8 的 LIS 為 5 7 8 。
而因為一節車廂可以接在現有的列車前面或後面。雖然表面上每次都有兩種選擇，但是只要選了某一邊開始接，之後的車廂必定也接在同一側（畢竟要保持重量的順序）。因此不只要求給定數列的 LIS ，也要求反序的數列之 LIS 。
雖然 LIS 有動態規劃（DP）的解法，但是時間複雜度為 Ｏ（ｎ ^ ２）。而我們可以採取貪心演算法（Greedy Algorithm）的精神去得出 LIS 的長度：
每當有一新數字進來之後，判斷此數有無比現在 LIS 結尾的數值大。
如果此數大於 LIS 的結尾，那就直接放到 LIS 結尾的後面，成為新的結尾。
反之，此數小於結尾，則用二分搜尋法（Binary Search）去找到在 LIS 由左數來第一個大於此數的數字，並將其替代掉。（因為此數較小，所以「可能」可以接得更長）
當所有數字都依序檢查過後，即可得出 LIS 的長度。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
