[LeetCode] 300. Longest Increasing Subsequence

轉自LeetCode

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

<Solution>

和  674. Longest Continuous Increasing Subsequence 同思路，但比較簡單點

• 利用 dp 的想法，去計算當每個位置 i 可以形成合法的 subsequence 時，最長的長度是多少

• 過程中並記錄，整體最長的長度是多少

code 如下

Java
Time complexity O(n^2)

kotlin
Time complexity O(n^2)

另一種想法，使用binary search，可以把時間複雜度降到 O(nlogn)

用一個額外的 list，紀錄目前最長的 subsequence，初始值是 nums[0]

當 nums[i] 大於 list 的最後一個數字時，直接加到 list 中，因為符合題意，是升冪

當 nums[i] 小於等於 list 的第一個數字時，直接取代第一個數字

為什麼可以這樣做呢？

首先，因為我們是按順序歷遍，當在 nums[i] 遇到一個比list 的第一個數字小的值

代表從位置 i 開始，有可能有機會找到一個新的 increasing subsequence

且取代第一個數字，並不會增加現有長度，也就是目前的最大值並沒有變化

至於之後出現更大的值後，會不會出現例外

這時候就是使用 binary search 的時候了，用 [4,10,4,3,8,9] 來舉例

到 i = 2 的時候，list = [4,10]

i = 3 時，list = [3,10]，可以看到長度並沒有變

i = 4 時，3 < nums[4] = 8 <= 10，這時候用 binary search 找到第一個不小於 8 的位置

然後取代變成 8，所以list會變成 [3,8]

i = 5 時，list = [3,8,9]

最後的 list.size 就是答案

有一個要注意的地方是，list 裡面的 subsequence 並不會是正確的 subsequence

因為題目是要求長度，所以可以用這種方式

舉例，當 nums = [4,5,6,3]，最後的 list = [3,5,6]，長度是對的，但 subsequence 是錯的

kotlin