给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
- 说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
思路
- 全局的最长递增子序列，不需要连续
- 最长连续递增子序列：
- dp[i]表示以第i个元素为结尾的连续递增子序列的长度
- $$ dp[i] = max(dp[i],dp[i-1]+1) $$
- 全局的最长递增子序列：
- dp[i]表示以第i个元素为结尾的[0,i)连续递增子序列的长度
- 空间复杂度优化
- tail[i]表示以第i个元素为结尾的[0,i)连续递增子序列的最后一个元素的值
代码
- 最长上升连续子序列
class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length <= 1) return nums.length;
int maxLen = 1;
int len = nums.length;
int[] dp = new int[len];
dp[0] = 1;
for (int i = 1;i < len; i++) {
if (nums[i] >= nums[i-1]) { // 非严格递增
dp[i] = dp[i-1]+1;
}else{
dp[i] = 1;
}
maxLen = Math.max(maxLen,dp[i]);
}
return maxLen;
}
}
- 全局最长递增子序列
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {return 0;}
int[] dp = new int[nums.length];
int res = 0;
Arrays.fill(dp,1);// 初始状态都为1
for (int i = 0;i < nums.length;i++) {
// 求 [0,i) 区间内的最长递增序列的最大长度，为dp[i]
for (int j = 0;j < i;j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i],dp[j] + 1);// 逐渐增加，从局部最优全局最优
}
}
res = Math.max(res,dp[i]);
}
return res;
}
}
- 动态规划 + 二分搜索
class Solution {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int res = 0;
for (int num : nums) {
int i = 0,j = res;
// 查找插入的位置，第一个比num小的数字的下一个位置
while(i < j) {
int m = (i + j) / 2;
if (tails[m] < num) {
i = m + 1;
}else {
j = m;
}
}
tails[i] = num;// 更新i处的数字，使其保持最小，给剩余数据添加可以增长的空间
// num大于tail的最大值
if (res == j) {res++;}
}
for(int t : tails){
System.out.print(t+" ");
}
return res;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
