LeetCode 300 Longest Increasing Subsequence
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?
DiffcultyMedium
Similar Problems
LeetCode 300 Increasing Triplet Subsequence Medium
LeetCode 300 Russian Doll Envelopes Hard
Analysis
注意：LIS 不要求递增子序列的元素是连续的
这道题是求最值的问题，应该采用动态规划来实现。
dp[i] 表示以第 i 个元素为结尾的最长递增子序列
思路一 转化为 LCS 问题求解 把序列 L 先进行排序，变成序列 X，那么显然 X 与 L 的最长公共子序列即为 L 的最长递增子序列。这样就把求最长递增子序列的问题转化为求最长公共子序列问题 LCS 了。
思路二 动态规划法
设 dp[i] 表示 L 中以 A[i] 结尾的最长递增子序列的长度。则有如下的递推方程：
dp[i] = max(dp[j]) + 1, j < i && A[j] < A[i]
= 1, j < i && not exist A[j] < A[i]
由于一个字符也能至少组成 LIS，因此 dp[i] 至少是 1。
上述递推方程的意思是，在求以 A[i] 结尾的最长递增子序列时，找出一个以 A[j] 结尾的（ j < i）的最长递增子序列, 那么 dp[i] 就等于这个最长递增子序列加 1 ，用公式表达就是:
dp[i] = {max(dp[j])} + 1。 注意，这里的 dp[j] 是 i 位置之前的所有子序列中最长的一个子序列，并非离 A[i] 越近的子序列就越长。
动态规划法的时间复杂度是 O(N^2)。
思路三 二分查找法 动态规划法之所以慢，是因为对于每一个新的位置 j 都需要遍历 j 之前的所以位置，找出之前位置最长递增子序列长度。那么我们是不是可以有一中方法能不用遍历之前所有的位置，而可以更快的确定 i 的位置呢？ 这就需要申请一个长度为 N 的空间，B[N]，用变量len记录现在的最长递增子序列的长度。然后通过二分查找来确定要找的元素。这样，算法的时间复杂度就降到了 O(NlogN)。
在第二种算法中，在计算每一个 dp[i] 时，都要找出最大的 dp[j]，其中 j < i，由于 dp(j) 没有顺序， 只能顺序查找满足 A[j] < A[i] 最大的 dp[j]，如果能将让 dp[j] 有序，就可以使用二分查找，这样算法的时间复杂度就可能降到 O(nlogn)。 于是想到用一个数组 B 来存储“子序列的”最大递增子序列的最末元素， 即有 B[f(j)] = A[j]，在计算 dp[i] 时，在数组B中用二分查找法找到满足 j < i 且 B[f(j)] = A[j] < A[i] 的最大的 j,并将 B[f[j]+1] 置为 A[i]。
Solutions
1、解法二
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size(), 1);
int res = 0;
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
res = max(res, dp[i]);
}
return res;
}
};
2、二分查找
int LIS_improve(vector<int> a) {
int n = a.size();
vector<int> LS(n, 1);
vector<int> B(a);
B[0] = -1; // 把B[0]设为最小，假设任何输入都大于-10000；
B[LS[0]] = a[0]; // 初始时，最大递增子序列长度为1的最末元素为a1
int p, r, mid; // p, r, mid 分别为二分查找的上界，下界和中点:
for(int i = 1; i < n; i++) {
p = 0;
r = LS[i - 1];
while(p <= r) { // 二分查找最末元素小于ai+1的长度最大的最大递增子序列；
mid = (p + r)/2;
if(B[mid] < L[i])
p = mid + 1;
else r = mid - 1;
}
B[p] = L[i]; // 将长度为p的最大递增子序列的当前最末元素置为ai+1;
if(p > LS[i]) LS[i]++; // 更新当前最大递增子序列长度；
}
return LS[n - 1]
}
3、二分查找
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int i = 0, len = 1, *end = (int *)alloca(sizeof(int) * (n + 1));
end[1] = nums[0]; //初始化：长度为1的LIS末尾为d[0]
for (i = 1; i < n; i++) {
int pos = upper_bound(end, 1, len, nums[i]); //找到插入位置
end[pos] = nums[i];
if (len < pos) //按需要更新LIS长度
len = pos;
}
return len;
}
// 在非递减序列 arr[s..e]（闭区间）上二分查找第一个大于等于key的位置，如果都小于key，就返回e+1
int upper_bound(int arr[], int s, int e, int key) {
int mid;
if (arr[e] <= key)
return e + 1;
while (s < e) {
mid = s + (e - s) / 2;
if (arr[mid] <= key)
s = mid + 1;
else
e = mid;
}
return s;
}
};
3、二分查找（Java）
public class LIS {
public static int lengthofLCS(int[] arr){
// 辅助变量
int[] MaxV = new int [arr.length+1]; // 记录递增子序列 LIS 的末尾元素最小值
int nMaxLength = 1; // 当前LIS的长度
int [] LIS = new int[arr.length+1]; //LIS[i]记录的是以第i个元素为结尾的最长序列的长度
// 初始化
MaxV[0] = -100;
MaxV[nMaxLength] = arr[0];
LIS[0] = 0;LIS[1] = 1;
for(int i=1;i < arr.length;i++){
if(arr[i] > MaxV[nMaxLength]){
MaxV[++nMaxLength] = arr[i];
LIS[i] = LIS[i-1]+1;
}
else{
// 新元素 更小，更有“潜力”，替换大的元素
int index = binarySearch(MaxV,arr[i],0,nMaxLength);
//*
LIS[i] =index;
MaxV[index] = arr[i];
}
}
Arrays.sort(LIS);
return LIS[LIS.length-1];
}
// 在MaxV数组中查找一个元素刚刚大于arr[i]
// 返回这个元素的index
public static int binarySearch(int []arr, int n, int start, int end){
while(start < end){
int mid = (start + end)/2;
if(arr[mid] < n){
start = mid+1;
}
else if(arr[mid]> n) {
end = mid -1;
}
else
return mid;
}
return end;
}
}