LeetCode 300. Longest Increasing Subsequence最長上升子序列 (C++/Java)
- 2019 年 10 月 20 日
- 筆記
題目：
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 is4.
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?
分析：
給定一個無序的整數數組，找到其中最長上升子序列的長度。
注意此題不要求上升子序列是連續的，我們可以去觀察這樣一個問題，已知一個序列[16，17，2，3，4]其最大上升子序列是[2，3，4]如果這時候又來一個20，我們這樣來看。
如果以4為結尾和20組合，那麼我們此時的序列則是[16，17，2，3，4，20]其最大上升子序列是[2，3，4，20]，最大長度也就是3+1=4(原來序列以4為結尾的最大上升子序列的長度+1)。
如果以3為結尾和20組合，那麼我們此時的序列則是[16，17，2，3，20]其最大上升子序列是[2，3，20]，最大長度是2+1。
如果以2為結尾和20組合，那麼我們此時的序列則是[16，17，2，20]其最大上升子序列是[2，20]，最大長度是1+1。
你可能會問這時候最大上升子序列不應該是[16，17，20]嗎？要記住，此時我們求的是以2結尾的最大上升子序列，所以只能是[2，20]。
如果以17為結尾和20組合，那麼我們此時的序列則是[16，17，20]其最大上升子序列是[16，17，20]，最大長度是2+1。
如果以16為結尾和20組合，那麼我們此時的序列則是[16，20]其最大上升子序列是[16，20]，最大長度是1+1。
我們可以從頭遍曆數組，每新來一個元素，便去和以前所有元素去相比，如果新來的元素比當前元素大，則意味著新來的元素可以和以當前元素為結尾的最大上升子序列構成新的最大上升子序列，且新最大上升子序列的長度等於以當前元素為結尾的最大上升子序列的長度+1，這樣聽起來可能繞口些。我們開闢一個新的數組，大小和原數組一樣大，對應位置存儲著以此元素為結尾的最大上升子序列的長度。
| 10 | |||||||
| 1 | |||||||
| 10 | 9 | ||||||
| 1 | 1 | ||||||
| 10 | 9 | 2 | |||||
| 1 | 1 | 1 | |||||
| 10 | 9 | 2 | 5 | ||||
| 1 | 1 | 1 | 2 | ||||
| 10 | 9 | 2 | 5 | 3 | |||
| 1 | 1 | 1 | 2 | 3 | |||
| 10 | 9 | 2 | 5 | 3 | 7 | ||
| 1 | 1 | 1 | 2 | 2 | 3 | ||
| 10 | 9 | 2 | 5 | 3 | 7 | 101 | |
| 1 | 1 | 1 | 2 | 2 | 3 | 4 | |
| 10 | 9 | 2 | 5 | 3 | 7 | 101 | 18 |
| 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 |
每新來一個元素，都要和前面的每一個元素為結尾的序列去比較能否成為新的上升子序列。最後返回數組中最大的值，即是最大上升子序列的長度，這樣時間複雜度是O(n^2)。
現在我們再來說一下O(nlogn)的方法，我們來利用二分搜索來維護一個最有希望的上升子序列的數組dp。
我們知道如果一個序列，[10，20，30，1，2，3.....]，很明顯1,2,3要比10,20,30更有希望構成最大上升子序列。
給定數列[10，20，30，1，2，3，5]。
先來10，那麼此時的最有希望的上升子序列dp：[10].
20，dp：[10，20]
30，dp：[10，20，30]
此時新加進來1，利用二分搜素，將1替換掉10，此時的最有希望的上升子序列為[1，20，30]，你可能會問，1在30的後面，無法和20,30構成上升子序列，的確，但是我們要求的是最有希望的，且我們的數組的大小就是最大的上升子序列的長度，如果後面的元素無法構成更大的上升子序列，那麼當前數組的大小也已經記錄下之前的最大上升子序列的長度，這點不用擔心。
1，dp：[1，20，30]
2，dp：[1，2，30]
3，dp：[1，2，3]
5，dp：[1，2，3，5]
此時的dp正是我們求的最有希望的上升子序列，且它的長度正是最大上升子序列的長度。
如果數列是[10，20，30，1，2]
最後求的dp會是[1，2，30]，雖然這無法構成上升子序列，但此時數組的大小，正是由之前10,20,30所擴充的，也保存了最大上升子序列的長度。
程式：
C++
//Dynamic class Solution { public: int lengthOfLIS(vector<int>& nums) { if(nums.size() == 1) return 1; int longest = 0; vector<int> res(nums.size(), 1); for(int i = 1; i < nums.size(); ++i){ for(int j = i; j > 0; j--){ if(nums[i] > nums[j-1]){ res[i] = max(res[i], res[j-1]+1); } } } for(auto n:res){ if(longest < n) longest = n; } return longest; } };
//Dynamic Programming with Binary Search class Solution { public: int lengthOfLIS(vector<int>& nums) { if(nums.size() == 0) return 0; vector<int> res; res.push_back(nums[0]); for(int i = 1; i < nums.size(); ++i){ int index = binarySearch(res, nums[i]); if(index == -1) res[0] = nums[i]; else if(index < -1) res.push_back(nums[i]); else res[index] = nums[i]; } return res.size(); } int binarySearch(vector<int>& v, int num){ if(num < v[0]) return -1; if(num > v[v.size()-1]) return -(v.size()+1); int l = 0; int r = v.size()-1; int mid; while(l <= r){ mid = l + (r-l)/2; if(num < v[mid]) r = mid-1; else if(num > v[mid]) l = mid+1; else return mid; } return l; } };
Java
//Dynamic Programming with Binary Search class Solution { public int lengthOfLIS(int[] nums) { if(nums.length == 0) return 0; int[] res = new int[nums.length]; int size = 0; for(int i = 0; i < nums.length; ++i){ int index = Arrays.binarySearch(res, 0, size, nums[i]); if(index < 0) index = -(index+1); res[index] = nums[i]; if(index == size) size++; } return size; } } //Java binarySearch // [1] 該搜索鍵在範圍內，但不是數組元素，由1開始計數，得“ - 插入點索引值”； // [2] 該搜索鍵在範圍內，且是數組元素，由0開始計數，得搜索值的索引值； // [3] 該搜索鍵不在範圍內，且小於範圍（數組）內元素，返回–(fromIndex + 1)； // [4] 該搜索鍵不在範圍內，且大於範圍（數組）內元素，返回 –(toIndex + 1)。
