给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
简单解法
从动态规划的角度思考，可以开辟一个数组保存原数组每个位置的最长上升子序列的长度。当遍历到原数组的位置时，在当前位置向前找到比当前值小的最大上升子序列的长度的长度，可能有点绕。
比如在[10,9,2,5,3,7,101,18] 中，遍历到7位置时，在7之前5和3的最长上升子序列的长度都是2，且都比7小，那么7这个位置的最长上升子序列的长度就是3了 。
dp[i] = Math.max(dp[j] + 1, dp[i]);
完整代码：
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n == 0 || n == 1) {
return n;
}
int[] dp = new int[n];
dp[0] = 1;
int res = 0;
for (int i = 1; i < n ; ++i) {
dp[i] = 1;
for (int j = 0 ; j < i ; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
}
优化做法
优化好的时间复杂度是O(nlogn), 从时间复杂度的要求上来看，做内层循环时可以使用二分查找，正好满足优化后的要求，那么问题来了，一个完全无序的数组怎么使用二分查找？下面分析一下。
数组：[10,9,2,5,3,7,101,18]
- 第一次遍历 10, ==> dp[0] = 1;
- 第二次遍历 10, 9 ==> dp[1] = 1;
- 第三次遍历 10, 9, 2 ==> dp[2] = 1;
- 第四次遍历 10, 9, 2, 5 ==> dp[3] = 2;
- 第五次遍历 10, 9, 2, 5, 3 ==> dp[4] = 2;
不知道各位观察到规律没有，第一次遍历、第二次遍历和第三次遍历的结果都是1，第四次遍历结果是2，只要第三次之后的结果比2大，那么结果就是2，这样的话10和9，对我们来说就没有意义了。如果去掉10和9，后续是2, 5, 3，如果下一个值是4，那么结果是3，5也就没必要保留了，这样剩下2和3 ，就是一个有序的数组了。
也就是说在相同结果长度的情况下，我们每个位置都保留最小的数组值，这样就会生成一个有序的数组，就可以使用二分查找了。
下面上代码
class Solution {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
if (n == 0 || n == 1) {
return n;
}
int[] dp = new int[n + 1];
// 保证原数组中的每次元素都比新数组初始位置的大
dp[0] = Integer.MIN_VALUE;
int top = 0;
int j = 0, end = 0, low = 0;
for (int i = 0; i < n ; ++i) {
low = 0;
end = top;
// 二分查找 找到dp数组中第一个小于 nums[i]的位置
while (low <= end) {
int mid = (low + end) / 2;
if (dp[mid] < nums[i]) {
j = mid;
low = mid + 1;
} else {
end = mid - 1;
}
}
// dp数组中第一个小于 nums[i]的位置 后一个位置赋值为nums[i]
dp[j + 1] = nums[i];
// 因为会替换dp中的值，所以top保留的就是最长上升子序列的长度
if (j + 1 > top) {
top = j + 1;
}
}
return top;
}
}
完整代码如上所示，我刷了不少题，但是这道题觉得比较有代表性。
