LeetCode刷题-动态规划- Longest Increasing Subsequence
文章目录
题目:
给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4
解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
说明:
- 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(_n2_) 。
进阶:你能将算法的时间复杂度降低到 O(_n_log_n_) 吗?
思路:构建一个数组dp[i]用于存放到相应位置时最长的上升子序列长度,那么需要比较脚标i前面的所有比nums[i]小的数的dp值,找到其中最大的dp值然后加1。
dp[i]=Math.max(dp[j]+1,dp[i])
public static int lengthOfLIS(int[] nums) {
//数组为空时返回0
if(nums.length==0||nums==null){
return 0;
}
int[]dp=new int[nums.length];//新建数组dp,用于放nums对应角标处最长上升数组dp的长度
int max=1;//若整个数组都降序,则max为1;
for (int i=0;i<nums.length;i++){
dp[i]=1;//先填充最小值1
//找出nums[i]前面所有数中比nums[i]小的数
for (int j=0;j<i;j++){
if (nums[i]>nums[j]){
//将dp[j]+1与原dp[i]最大值赋给新dp[i]
dp[i]=Math.max(dp[j]+1,dp[i]);
}
}
max=Math.max(max,dp[i]);//不断更新最长的上升数组长度
}
return max;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论