300.最长上升子序列

题目难度:中等

给定一个无序的整数数组,找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。

说明:

  • 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。

  • 你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

动态规划

public int lengthOfLIS(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
Arrays.fill(dp,1);
for (int i = 1; i <len; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]){
dp[i] = Math.max(dp[j] +1 ,dp[i]);
}
}
}
int res = dp[0];
for (int i = 0; i < len; i++) {
if (res < dp[i]){
res = dp[i];
}
}
return res;
}

一种是DP也就是动态规划,很简单,第i个元素之前的最小上升子序列的长度无非就是max(dp[i],dp[j]+1)

复杂度分析:

时间复杂度 O(N^2)

空间复杂度 O(N)

动态规划+二分查找

public int lengthOfLIS(int[] nums){
int[] dp = new int[nums.length];
int res = 0;
for (int num: nums){
int i=0, j=res;
while(i < j){
int m = (i + j) / 2;
if (dp[m] < num){
i = m+1;
}
else j = m;
}
dp[i] = num;
if (res == j) res++;
}
return res;
}

另一种做法就是二分查找法,也很简单,无非就是再新建一个数组,然后第一个数先放进去,然后第二个数和第一个数比较,如果说大于第一个数,那么就接在他后面,如果小于第一个数,那么就替换,一般的,如果有i个数,那么每进来一个新的数,都要用二分查找法来得知要替换在哪个位置的数。

复杂度分析:

时间复杂度 O(NlogN)

空间复杂度 O(N)