# Longest Increasing Subsequence - tags: [[DP_Sequence](# "單序列動態規劃，通常使用 f[i] 表示前i個位置/數字/字母... 使用 f[n-1] 表示最后返回結果。")] ### Source - lintcode: [(76) Longest Increasing Subsequence](http://www.lintcode.com/en/problem/longest-increasing-subsequence/) - [Dynamic Programming | Set 3 (Longest Increasing Subsequence) - GeeksforGeeks](http://www.geeksforgeeks.org/dynamic-programming-set-3-longest-increasing-subsequence/) ### Problem Given a sequence of integers, find the longest increasing subsequence (LIS). You code should return the length of the LIS. #### Example For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3 For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4 #### Challenge Time complexity O(n^2) or O(nlogn) #### Clarification What's the definition of longest increasing subsequence? - The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. - [https://en.wikipedia.org/wiki/Longest_common_subsequence_problem](https://en.wikipedia.org/wiki/Longest_common_subsequence_problem) ### 題解 由題意知這種題應該是單序列動態規劃題，結合四要素，可定義`f[i]`為前`i`個數字中的 LIC 數目，那么問題來了，接下來的狀態轉移方程如何寫？似乎寫不出來... 再仔細看看 LIS 的定義，狀態轉移的關鍵一環應該為數字本身而不是最后返回的結果(數目)，那么理所當然的，我們應定義`f[i]`為前`i`個數字中以第`i`個數字結尾的 LIS 長度，相應的狀態轉移方程為`f[i] = {1 + max{f[j]} where j < i, nums[j] < nums[i]}`, 該轉移方程的含義為在所有滿足以上條件的 j 中將最大的`f[j]` 賦予`f[i]`, 如果上式不滿足，則`f[i] = 1`. 具體實現時不能直接使用`f[i] = 1 + max(f[j])`, 應為若`if f[i] < 1 + f[j], f[i] = 1 + f[j]`. 最后返回 `max(f[])`. ### Python ~~~ class Solution: """ @param nums: The integer array @return: The length of LIS (longest increasing subsequence) """ def longestIncreasingSubsequence(self, nums): if not nums: return 0 lis = [1] * len(nums) for i in xrange(1, len(nums)): for j in xrange(i): if nums[j] <= nums[i] and lis[i] < 1 + lis[j]: lis[i] = 1 + lis[j] return max(lis) ~~~ ### C++ ~~~ class Solution { public: /** * @param nums: The integer array * @return: The length of LIS (longest increasing subsequence) */ int longestIncreasingSubsequence(vector<int> nums) { if (nums.empty()) return 0; int len = nums.size(); vector<int> lis(len, 1); for (int i = 1; i < len; ++i) { for (int j = 0; j < i; ++j) { if (nums[j] <= nums[i] && (lis[i] < lis[j] + 1)) { lis[i] = 1 + lis[j]; } } } return *max_element(lis.begin(), lis.end()); } }; ~~~ ### Java ~~~ public class Solution { /** * @param nums: The integer array * @return: The length of LIS (longest increasing subsequence) */ public int longestIncreasingSubsequence(int[] nums) { if (nums == null || nums.length == 0) return 0; int[] lis = new int[nums.length]; Arrays.fill(lis, 1); for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[j] <= nums[i] && (lis[i] < lis[j] + 1)) { lis[i] = lis[j] + 1; } } } // get the max lis int max_lis = 0; for (int i = 0; i < lis.length; i++) { if (lis[i] > max_lis) { max_lis = lis[i]; } } return max_lis; } } ~~~ ### 源碼分析 1. 初始化數組，初始值為1 1. 根據狀態轉移方程遞推求得`lis[i]` 1. 遍歷`lis` 數組求得最大值 ### 復雜度分析 使用了與 nums 等長的空間，空間復雜度 O(n)O(n)O(n). 兩重 for 循環，最壞情況下 O(n2)O(n^2)O(n2), 遍歷求得最大值，時間復雜度為 O(n)O(n)O(n), 故總的時間復雜度為 O(n2)O(n^2)O(n2). # Follow up 上述問題均只輸出最大值，現在需要輸出 LIS 中的每一個原始元素值。 ### 題解1 - LIS 由于以上遞歸推導式只能返回最大值，如果現在需要返回 LIS 中的每個元素，直觀來講，構成 LIS 數組中的值對應的原數組值即為我們想要的結果。我們不妨從后往前考慮，依次移除 lis[i] 數組中的值(減一)和索引，遇到和 lis[i]的值相等的 LIS 時即加入到最終返回結果。 ### Java ~~~ import java.util.*; public class Solution { /** * @param nums: The integer array * @return: LIS array */ public int[] longestIncreasingSubsequence(int[] nums) { if (nums == null || nums.length == 0) return null; int[] lis = new int[nums.length]; Arrays.fill(lis, 1); for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[j] <= nums[i] && (lis[i] < lis[j] + 1)) { lis[i] = lis[j] + 1; } } } // get the max lis int max_lis = 0, index = 0; for (int i = 0; i < lis.length; i++) { if (lis[i] > max_lis) { max_lis = lis[i]; index = i; } } // get result int[] result = new int[max_lis]; for (int i = index; i >= 0; i--) { if (lis[i] == max_lis) { result[max_lis - 1] = nums[i]; max_lis--; } } return result; } public static void main(String[] args) { int[] nums = new int[]{5, 4, 1, 2, 3}; Solution sol = new Solution(); int[] result = sol.longestIncreasingSubsequence(nums); for (int i : result) { System.out.println(i); } } } ~~~ 關于`// get result` 那一節中為何`max_lis` 自減一定是會得到最終想要的結果？假如有和其一樣的lis如何破？根據 DP 中狀態的定義可知正好為其逆過程，只不過答案不唯一，反向輸出的答案輸出的是最靠右的結果。