Leetcode 300.最长上升子序列
2024-09-08 16:53:06
最长上升子序列
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:
- 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
直接用DP求解,算法如下:时间复杂度为O(N^2)
①最优子问题
设lis[i] 表示索引为 [0...i] 上的数组上的 最长递增子序列。初始时,lis[i]=1,注意,在DP中,初始值是很重要的,它是整个算法运行正确的关键。而初始值 则可以 通过 画一个小的示例来 确定。
当 arr[i] > arr[j],lis[i] = max{lis[j]}+1 ;其中,j 的取值范围为:0,1...i-1
当 arr[i] < arr[j],lis[i] = max{lis[j]} ;其中,j 的取值范围为:0,1...i-1
class Solution {
public int lengthOfLIS(int[] nums) {
int length=nums.length;
if(nums==null || length==0) return 0;
int[] dp=new int[length];
for(int i=0;i<length;i++){
dp[i]=1;
}
for(int i=1;i<length;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]&&dp[j]+1>dp[i]){
dp[i]=dp[j]+1;
}
}
}
int max=dp[0];
for(int i=1;i<length;i++){
if(max<dp[i]){
max=dp[i];
}
}
return max;
}
}
最新文章
- 添加 Pool Member - 每天5分钟玩转 OpenStack(123)
- 002-添加网站ico图标
- jQuery DOM操作
- -bash: sudo: command not found Error and Solution
- Team Foundation Server简介
- hiho_1053_居民迁移
- 验证dictionary重复键
- jni编译non-numeric second argument to `wordlist&#39; function错误
- Unity NGUI实现技能CD效果
- 面向对象设计模式之Flyweight享元模式(结构型)
- 关于Layouts的分类
- [跟我学spring][Bean的作用域]
- MVC超链接
- Java数据类型及类型转换
- cellmap 基站查询 for android
- springCloud之配置中心学习
- arm-cache coherency
- 11.3 Daily Scrum
- uva 10983 Buy one, get the rest free 二分判定层次图
- HDU 1160 FatMouse&#39;s Speed (最长上升子序列)