- 链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/
解法一 #
class Solution {
public int lengthOfLIS(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
Arrays.fill(dp, 1);
int maxx = 1;
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[j] + 1, dp[i]);
}
}
maxx = Math.max(maxx, dp[i]);
}
return maxx;
}
}
- 时间复杂度：$O(n^2)$，其中 $n$ 为数组 $\textit{nums}$ 的长度。动态规划的状态数为 $n$，计算状态 $dp[i]$ 时，需要 $O(n)$ 的时间遍历 $dp[0 \ldots i-1]$ 的所有状态，所以总时间复杂度为 $O(n^2)$。
- 空间复杂度：$O(n)$，需要额外使用长度为 $n$ 的 $dp$ 数组。
进阶 #
看了别人的解法
/**
20210802：动态规划：nums[j]<nums[i] 有 dp[i] = max(dp[i], dp[j] + 1) for j in [0, i)
n2，n
*/
// class Solution {
// public int lengthOfLIS(int[] nums) {
// //构建dp数组
// int [] dp =new int [nums.length];
// //max保存最大dp，最小为1
// int max=1;
// //初始都为1
// Arrays.fill(dp,1);
// //迭代
// for(int i=1;i<nums.length;i++){
// //j从0到i
// for(int j=0;j<i;j++){
// //符合递增情况时，dp选大的
// if(nums[j]<nums[i]) dp[i]=Math.max(dp[j]+1,dp[i]);
// }
// //保存每轮最大值
// max=Math.max(dp[i],max);
// }
// return max;
// }
// }
/**
20210802：贪心+二分
维护一个结果数组，
如果当前元素比结果数组的值都大的的话，就追加在结果数组后面（相当于递增序列长度加了1）；
否则的话用当前元素覆盖掉第一个比它大的元素
（这样做的话后续递增序列才有可能更长，即使并没有更长，
这个覆盖操作也并没有副作用哈，
当然这个覆盖操作可能会让最终的结果数组值并不是最终的递增序列值，
这无所谓）
nlogn,n
*/
class Solution {
public int lengthOfLIS(int[] nums) {
//结果
int ans = 0;
//结果数组
int[] cur = new int[nums.length];
//遍历
for (int num : nums) {
//若是首个元素、或当前元素大于结果数组的末尾元素，就追加
if (ans == 0 || cur[ans - 1] < num) {
cur[ans++] = num;
} else {
//二分法，当前元素覆盖第一个比它大于等于的元素，查找该位置
//注意，这种查找不一定存在的数的位置的二分：
//一般不写==，并且一般有一边不加减1
int l = 0;
int r = ans - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (cur[mid] < num) l = mid + 1;
else r = mid;
}
//进行覆盖
cur[l] = num;
}
}
//返回长度
return ans;
}
}