在这篇文章中，我们将带领您了解[LeetCode]LongestIncreasingSubsequence的全貌，同时，我们还将为您介绍有关(Java)LeetCode300.LongestIncre

在这篇文章中，我们将带领您了解[LeetCode] Longest Increasing Subsequence的全貌，同时，我们还将为您介绍有关(Java) LeetCode 300. Longest Increasing Subsequence —— 最长上升子序列、300. Longest Increasing Subsequence、521. Longest Uncommon Subsequence I - LeetCode、CF568E Longest Increasing Subsequence的知识，以帮助您更好地理解这个主题。

• [LeetCode] Longest Increasing Subsequence
• (Java) LeetCode 300. Longest Increasing Subsequence —— 最长上升子序列
• 300. Longest Increasing Subsequence
• 521. Longest Uncommon Subsequence I - LeetCode
• CF568E Longest Increasing Subsequence

[LeetCode] Longest Increasing Subsequence

Input: Output: 4 
Explanation: The longest increasing subsequence is,therefore the length is . [10,9,2,5,3,7,101,18][2,101]4

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n,1);
        int res = 0;
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (nums[j] < nums[i])
                    dp[i] = max(dp[i],dp[j]+1);
            }
            res = max(res,dp[i]);
        }
        return res;
    }
};

(Java) LeetCode 300. Longest Increasing Subsequence —— 最长上升子序列

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n²) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

解法一，O(n²)：

直观想一下，选中一个元素，以这个元素为结尾的子序列前面有多少个比他值小的元素，那么以它为结尾的上升子序列就是多少再加一。即当前状态可以由之前的一个或一些状态推导出来，所以可以用动态规划。建立一个一维数组dp，dp[i]表示以nums[i]结尾的最长上升子序列长度。初始都置为1。对于原数组每个元素，二重循环从头遍历原数组，每当找到一个比当前元素小的值，证明至少可以形成一个dp[j]+1的上升子序列，所以dp[i] = max(dp[i], dp[j] + 1)，而dp[j]之前已经求得。

解法二，O(n log n)：

还是想一下“人工”做这个题是什么过程。按照上面的例子来分析：

首先看到10，加入备选集，备选集合为{10}；

之后看到了9，没有形成上升序列，那么9不应该加入备选集合。但是因为9小于10，所以如果把10替换成9会增加接下来产生上升序列的机会，且并不影响备选集合元素的个数（因为是替换），所以替换掉，备选集现在有{9}；

遇到2道理同上，替换掉9，备选集变成{2}；

遇到5，这时候形成了上升序列，此时应该是添加到备选集合，变为{2,5}；

遇到3，没有形成上升序列，但还是道理同加入9的情况，如果此时把5替换成3，会增加接下来形成上升序列的机会，且备选集保持上升，并且个数也没变，所以替换掉5，备选集变成{2,3}；

遇到7，同遇到5，添加元素，备选集{2,3,7}；

遇到101，同上，备选集{2,3,7,101}；

遇到18，还是一样，虽然没有形成上升序列，但是如果把101替换掉，那么接下来形成上升序列的机会会增加，并且备选集的上升属性和元素个数都不变，所以替换，备选集变为{2,3,7,18}。

至此所有元素添加完毕，备选集的元素个数就是最长上升子序列长度。但这里注意，备选集里面的元素并不是最后最长子序列的元素。因为在寻找最长子序列的过程中，目标是尽可能的让以后形成上升序列的机会增加，所以进行了替换。

“人工”做出来之后，只要用程序实现思考过程就好。总结起来就是：

如果遇到的元素比备选集合里面的元素都大，那么就添加进去，使得上升序列长度增加；

如果遇到的元素比备选集合里最后一个元素小，那么代表它无法被添加到备选集。但是为了使后面得到上升序列的机会增加，需要在不破坏集合上升属性和元素总数的情况下，替换掉备选集中的元素，那么就是替换掉大于他的元素中最小的那个，这样才能满足条件。

这时候，发现备选集一直是保持有序，寻找替换元素的时候就可以用到二分查找，得到O(n log n)的时间复杂度。其中还要注意的是如果元素已经在备选集合中，是不需要任何操作的，因为它并不能增加上升序列的长度，也不会增加之后遇到上升序列的机会，所以直接跳过。

解法一（Java）

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int max = 1;
        for (int i = 0; i < nums.length; i++)
            dp[i] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j]);
                    max = max > dp[i] ? max : dp[i];
                }            
            }
        }
        return max;
}

解法二（Java）

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        List<Integer> dp = new ArrayList<>();
        dp.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            if (dp.contains(nums[i])) continue;
            else if (nums[i] > dp.get(dp.size()-1)) dp.add(nums[i]);
            else if (nums[i] < dp.get(dp.size()-1)) {
                int l = 0, r = dp.size()-1;
                while (l < r) {
                    int mid = l + (r - l) / 2;
                    if (dp.get(mid) < nums[i]) l = mid + 1;
                    else r = mid;
                }
                dp.set(r, nums[i]);
            }
        }
        return dp.size();
    }
}

300. Longest Increasing Subsequence

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?

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int []f = new int[nums.length];
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            f[i] = 1; //至少有自己一个递增子序列
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && f[i] <= f[j] + 1) {  //保证只比最大的大1个，前面乱序的不会乱加
                    f[i] = f[j] + 1;
                }
            }
            if (f[i] > max) {
                max = f[i];
            }
        }
        return max;
    }
}

Nums 1,3,5,2,8,4,6
Lis：  1,2,3,2,4,3

当做到第6位时，当j指针走到nums为2的时候lis[i]并不用更新，这是因为此时的lis[i]已经是4了，并没有小于等于lis[j]

521. Longest Uncommon Subsequence I - LeetCode

Question

521. Longest Uncommon Subsequence I

Solution

题目大意：给两个字符串，找出非共同子串的最大长度

思路：字符串相等就返回-1，不等就返回长度大的那个长度

Java实现：

public int findLUSlength(String a, String b) {
    int aLength = a.length();
    int bLength = b.length();
    if (aLength != bLength) return Math.max(aLength, bLength);
    if (a.equals(b)) return -1;
    return aLength;
}

2

public int findLUSlength(String a, String b) {
    if (a.equals(b)) return -1;
    return Math.max(a.length(), b.length());
}

CF568E Longest Increasing Subsequence

先留个坑，输出方案的地方还得再想想

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<stack>
#include<queue>
using namespace std;
typedef long long ll;

const int maxn = 100010;
const int INF = 1e9+7;

int n,m,len,cnt;
int a[maxn],b[maxn],c[maxn];
int pre[maxn],from[maxn],tmp[maxn],v[maxn];

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<''0'' || ch>''9''){ if(ch==''-'') f=-1; ch=getchar(); } while(ch>=''0'' && ch<=''9''){ s=s*10+ch-''0''; ch=getchar(); } return s*f; }

int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    m=read();
    for(int i=1;i<=m;i++) b[i]=read();
    sort(b+1,b+1+m);
//    for(int i=1;i<=n;i++) c[i]=INF;
    
    len=0;
    for(int i=1;i<=n;i++){
        if(~a[i]){
            int p=lower_bound(c+1,c+1+len,a[i])-c;
            pre[i]=from[p-1];
            from[p]=i;
            c[p]=a[i];
            if(len<p) len=p;
            
        }else{
            int k=1;
            for(int j=1;j<=m;++j){
                while(k<=len&&c[k]<b[j]) ++k;
                tmp[j]=k;
            }
            if(len<k) len=k;
            for(int j=m;j;j--){
                c[tmp[j]]=b[j];
                from[tmp[j]]=from[tmp[j]-1];
            }
        }
    }
    cnt=0;
    for(int i=from[len];i;i=pre[i]){
        tmp[++cnt]=i;
    }
    tmp[0]=n+1;
    tmp[cnt+1]=0;
    
    a[n+1]=INF; b[m+1]=INF;
    for(int i=cnt+1;i;i--){ // 找到b中填到lis位置上的数 
        int last=a[tmp[i]];
        for(int j=tmp[i]+1;j<tmp[i-1];j++){
            if(!~a[j]){
                int k=upper_bound(b+1,b+1+m,last)-b;
                if(k>m||b[k]>=a[tmp[i-1]]) break;
                v[k]=1;
                last=a[j]=b[k];
            }
        }
    }
    
    for(int i=1,j=1;i<=n;i++){
        if(!~a[i]){
            while(j<m&&v[j]) ++j;
            a[i]=b[j];
            v[j]=1;
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }printf("\n");
    
    return 0;
}

今天关于[LeetCode] Longest Increasing Subsequence的分享就到这里，希望大家有所收获，若想了解更多关于(Java) LeetCode 300. Longest Increasing Subsequence —— 最长上升子序列、300. Longest Increasing Subsequence、521. Longest Uncommon Subsequence I - LeetCode、CF568E Longest Increasing Subsequence等相关知识，可以在本站进行查询。