[思路]LeetCode Problems- 300. Longest Increasing Subsequence
在做完 [思路]LeetCode Problems- 441. Arranging Coins 這題之後 隔天一早十點多起床想說再繼續挑戰一題來試看看 於是按下了LeetCode首頁右下的"Pick One"鍵 跳出了這一題, 原文如下: Given an unsorted array of integers, find the length of longest increasing subsequence. For example, Given [10, 9, 2, 5, 3, 7, 101, 18] , The longest increasing subsequence is [2, 3, 7, 101] , therefore the length is 4 . Note that there may be more than one LIS combination, it is only necessary for you to return the length. Your algorithm should run in O( n 2 ) complexity. Follow up: Could you improve it to O( n log n ) time complexity? Credits: Special thanks to @pbrother for adding this problem and creating all test cases. 當下看到時有點傻眼 天啊這題目到底想要求甚麼啊~?? 多看幾次才逐漸明瞭 好像是要求這有序數列裡 最長的遞增數列 的個數 如上述那一串數列中,最長的遞增數列為 2 3 7 101 其長度是4 但就數列"內容"來說這不算是唯一的答案, 也應該能寫成2 5 7 101 或者是2 3 7 18 這類 當發覺答案不會是唯一解的時候,其實內心覺得有點怕怕的@@ (心中OS開始 ) 認真在看題目想如何解的時候,腦袋想法變得十分稀少,不知道要如何下手 相信在寫code的初學者或大學生(例如我)...