本题用动态规划和二分查找可解
一、题目
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n^2) 。
进阶:你能将算法的时间复杂度降低到 O(n log n) 吗?
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
二、分析
2.1 题目分析
原始的数组是一个无序数组，要从无序数组中找到最长上升子序列。这个子序列的元素在原始数组中不要求是连续的，并且子序列的元素必须是严格递增的。
也就是说如果原始数组是 [10,9,2,5,3,7,101,18]，那么 [2,3,7,101]就是一个最长的上升子序列。
2.2 回溯？
如果我们用回溯法来遍历数组，时间复杂度是2^n次方，这是不能接收的。
2.3 动态规划
既然题目要求的是最长子序列的长度，那么我们可以使用动态规划，启动dp[i]保存的就是以第 i个数字结尾的最长子序列的长度。
也就是说，如果原始数组src [] = {10, 3, 5, 2};
则dp[] 应为是 {1, 1, 2, 1}
我们应该把状态转移公式求出来。
动态规划的状态转移方程
基于上面的公式，我们可以写出下面的代码
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length]; //记录以第i个数组结尾的最长上升序列
int res = 0;
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) { // dp[i] = max(dp[j] + 1) && dp[j] < dp[i] && 0 <= j < i
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return res;
}
代码的时间复杂度是 n^2
2.4 动态规划+二分查找
如果将时间复杂度提高到nlogn，那么就需要修改一下思路。
我们用dp[i]保存所有长度为i + 1的上升序列的最后一个元素中最小的那一个。
因此，对于src[] = {10, 9, 2, 5, 3, 7, 101, 18}
遍历数组，dp对应为
i = 0 dp = {10}
i = 1 dp = {9}
i = 2 dp = {2}
i = 3 dp = {2, 5}
i = 4 dp = {2, 3}
i = 5 dp = {2, 3, 7}
i = 6 dp = {2, 3, 7, 101}
i = 7 dp = {2, 3, 7, 18}
由于dp数组是严格上升的，那么我们可以用二分查找的方式更新dp数组，这样总的时间复杂度就是nlogn。
代码如下
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length]; // dp[i] 标识所有长度为i+1的序列中，最小的序列尾数
int maxLen = 1;
dp[0] = nums[0];
for (int cur : nums) {
if (cur > dp[maxLen - 1]) {
dp[maxLen] = cur;
maxLen++;
} else {
int start = 0;
int end = maxLen - 1;
while (start < end) { //二分查找
int mid = (start + end) /2;
if (cur > dp[mid]) {
start = mid + 1;
} else {
end = mid;
}
}
dp[start] = cur;
}
}
return maxLen;
}
