2018-03-18 21:36:38
在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。许多与数学、算法、随机矩阵理论、表示论相关的研究都会涉及最长递增子序列。解决最长递增子序列问题的算法最低要求O(n log n)的时间复杂度，这里n表示输入序列的规模。
一、朴素解法
首先先介绍一个非常朴素的解法，L[i]是以nums[i]结尾的最长上升子序列长度，很容易写出如下的递推式：
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.
显然时间复杂度为O(n ^ 2)。
public int LIS_Naive(int[] nums) { int[] d = new int[nums.length]; for (int i = 0; i < nums.length; i++) { int max = 0; for (int j = 0; j < i; j++) { if (nums[j] < nums[i] && d[j] > max) max = d[j]; } d[i] = max + 1; } int res = 0; for (int i = 0; i < nums.length; i++) { if (d[i] > res) res = d[i]; } return res; }
二、优化解法
LIS问题最优的解法并不是在O(n^2)的时间复杂度完成求解，在最优的算法里可以在O(nlogn)的时间复杂度完成求解。
d[k]：长度为k + 1的上升子序列的最末元素，若有多个长度为k + 1的上升子序列，则记录最小的那个最末元素。
这里可以使用lowerBound函数来加速寻找。
public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length]; Arrays.fill(dp, Integer.MAX_VALUE); for (int i : nums) { int idx = lowerBound(dp, i); dp[idx] = i; } return lowerBound(dp, Integer.MAX_VALUE); } private int lowerBound(int[] nums, int k) { int lb = -1; int ub = nums.length; while (ub - lb > 1) { int mid = lb + (ub - lb) / 2; if (nums[mid] >= k) ub = mid; else lb = mid; } return ub; }
三、Follow Up
-
Number of Longest Increasing Subsequence
问题描述：
问题求解：
public int findNumberOfLIS(int[] nums) { int n = nums.length; int[] dp = new int[n]; int[] res = new int[n]; for (int i = 0; i < n; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { if (dp[j] + 1 > dp[i]) { dp[i] = dp[j] + 1; res[i] = res[j]; } else if (dp[j] + 1 == dp[i]) res[i] += res[j]; } } if (res[i] == 0) res[i] = 1; } int len = 0; for (int i = 0; i < n; i++) len = Math.max(len, dp[i]); int ans = 0; for (int i = 0; i < n; i++) { if (dp[i] == len) ans += res[i]; } return ans; }