动态规划LeetCode300最长上升子序列

2019/06/18 14:56
阅读数 4

在做这道题之前,我们先看一下什么是子序列。

 区分子串和子序列:

给定 "pwwkew" ,

子串是pww,wwk等很多个子串 是连在一起的

子序列是 pwk,pke等很多个子序列 ,但是子序列中的字符在字符串中不一定是连在一起的。 

 

题目描述:

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

示例:

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

可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n^2)
进阶: 你能将算法的时间复杂度降低到 O(n*log n) 吗?

 

思路:dp[i]代表以第i个元素结尾的最长上升子序列的长度。

 1 class Solution {
 2     public int lengthOfLIS(int[] nums) {
 3         if (nums.length==0) {
 4             return 0;
 5         }
 6         int[] dp=new int[nums.length];
 7         dp[0]=1;
 8         int LIS=1;
 9         for (int i=0; i<nums.length; i++) {
10             dp[i]=1;
11             for (int j=0; j<i; j++) {
12                 if (nums[i]>nums[j]&&dp[i]<dp[j]+1) {
13                     dp[i]=dp[j]+1;
14                 }
15             }
16             if (dp[i]>LIS) {
17                 LIS=dp[i];
18             }
19         }
20         return LIS;
21     }
22 }

上面这个算法的时间复杂度为O(n^2)。

 

 

待会补充一下O(n*log n) 的解法,这个解法是利用栈和二分查找,大家先思考一下。

欢迎评论,共同进步!!

 

 

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部