动态规划系列【2】最长递增子序列LIS

简介:
1
2
3
4
5
6
7
8
9
10
Given an unsorted array of integers, find the length of longest increasing subsequence.
For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.
Follow up: Could you improve it to O(n log n) time complexity?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
 
Subscribe to see which companies asked this question.

题意:无需多说。主要是这玩意有基础版O(n^2)和增强版O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public  class  Solution {
     public  int  lengthOfLIS( int [] nums) {
         int  length=nums.length;
         if (length== 0 ) return  0 ;
         int  max= 1 ;
         int [] d= new  int [length];
         for ( int  i= 1 ;i<length;i++){
             d[i]= 1 ;
             for ( int  j= 0 ;j<i;j++){
                 if (nums[j]<nums[i])
                   d[i]=Math.min(d[i],d[j]= 1 );
             }
             max=Math.max(d[i],max);
         }
         return  max;
       }
}

PS:思路参加http://www.hawstein.com/posts/dp-novice-to-advanced.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public  class  AscentSequence {
     public  int  findLongest( int [] A,  int  n) {
         // write code here
         int [] dp= new  int [n];
         int [] ends= new  int [n];
         ends[ 0 ]=A[ 0 ];
         dp[ 0 ]= 1 ;
         int  max= 1 ;
         int  r= 0 ,right= 0 ,l= 0 ,m= 0 ;
         for ( int  i= 1 ;i<n;i++){
             l= 0 ;
             r=right;
             while (l<=r){
                 m=(l+r)/ 2 ;
                 if (A[i]>ends[m]){
                     l=m+ 1 ;
                 } else {
                     r=m- 1 ;
                 }
             }
             //没明白
             right=Math.max(l,right);
             ends[l]=A[i];
             dp[i]=l+ 1 ;
             max=Math.max(dp[i],max);
         }
         return  max;
     }
}

用二分查找、辅助数组。


最后是打印出来最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public  static  int [] getLIS( int [] arr, int [] dp){
         int  maxlen= 0 ;
         int  index= 0 ;
         for ( int  i= 0 ;i<dp.length;i++){
             if (dp[i]>maxlen){
                 maxlen=dp[i];
                 index=i;
             }
         }
         System.out.println(index+ "" +maxlen);
         int [] list= new  int [maxlen];
         list[--maxlen]=arr[index];
         for ( int  j=index;j>= 0 ;j--){
             if (arr[j]<arr[index] && dp[j]+ 1 ==dp[index]){
                 list[--maxlen]=arr[j];
                 index=j;
             }
         }
         return  list;
     }

PS:首先找到dp中最大值及其索引index。然后去数组arr[index]中从右往左遍历。找到第一个小于arr[index]且dp[]+1==dp[index]的值作为倒数第二个数。一次往后重复此过程。



本文转自 努力的C 51CTO博客,原文链接:http://blog.51cto.com/fulin0532/1903095

相关文章
|
10月前
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
【动态规划刷题 15】最长定差子序列&& 最长的斐波那契子序列的长度
|
10月前
|
算法 JavaScript Go
【动态规划】最长递增子序列
【动态规划】最长递增子序列
|
7月前
|
算法 程序员 C#
C++二分查找算法的应用:最长递增子序列
C++二分查找算法的应用:最长递增子序列
|
2月前
|
算法 程序员
【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列
【算法训练-动态规划 二】【线性DP问题】连续子数组的最大和、乘积最大子数组、最长递增子序列
76 0
|
2月前
|
算法 程序员 索引
【算法训练-动态规划 三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离
【算法训练-动态规划 三】【双序列DP问题】最长重复子数组、最长公共子串、最长公共子序列、编辑距离
78 0
|
9月前
|
算法
【学会动态规划】 最长递增子序列(26)
【学会动态规划】 最长递增子序列(26)
25 0
|
9月前
|
算法
【学会动态规划】最长递增子序列的个数(28)
【学会动态规划】最长递增子序列的个数(28)
28 0
|
算法
Leecode 300. 最长上升子序列
Leecode 300. 最长上升子序列
52 0