最长递增子序列（LCS）

[编程题]最长递增子序列（LCS）

热度指数：321 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

给定一个序列 An = a1 ,a2 , ... , an ，找出最长的子序列使得对所有 i < j ，ai < aj 。求出这个子序列的长度

输入描述:

输入的序列

输出描述:

最长递增子序列的长度

示例1

输入

1 -1 2 -2 3 -3 4

输出

算法知识视频讲解

C/C++

LIFEFOR

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
vector<int> nums;
int res=0;
int n;
while(cin>>n) nums.push_back(n);
int len=nums.size();
vector<int> dp(len,1);
for(int i=1;i<len;i++){
for(int j=i-1;j>=0;j--){
if(nums[i]>nums[j]){
dp[i]=max(dp[j]+1, dp[i]);
}
}
}
for(int i=0;i<len;i++){
res=max(dp[i],res);
}
cout<<res;
return 0;
}

发表于 2020-06-22 14:34:55 回复(0)

菲尼克斯弗兰克

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] s = in.nextLine().split(" ");
        int[] arr = Arrays.stream(s).mapToInt(Integer::valueOf).toArray();
        // 最长上升子序列的长度LIS-二分查找
        int[] tmp = new int[arr.length];
        int tail = 0;
        for (int n : arr) {
            int l = 0, r = tail; // 左闭右开找左边界
            while (l < r) {
                int m = l + (r - l) / 2;
                if (tmp[m] < n) {
                    l = m + 1;
                } else {
                    r = m;
                }
            }
            tmp[l] = n;
            if (l == tail) tail++;
        }
        System.out.println(tail);
    }
}

发表于 2022-07-26 17:50:33 回复(0)

Heerh

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String[] str = scanner.nextLine().split(" ");
        //int len = str.length;
        int[] arr = new int[str.length];
        for(int i=0;i<str.length;i++){
            arr[i]=Integer.parseInt(str[i]);
        }
        int max = lengthOfLIS(arr);
        System.out.println(max);
    }
    static int lengthOfLIS(int[] arr){
        //数组定义：dp[i]为从0到i的最长递增子序列值，base case ：自身并入计算结果中
        int[] dp = new int[arr.length];
        Arrays.fill(dp,1);
        int max = arr[0];
        for(int i = 0;i < arr.length; i++){
            for(int j = 0; j <= i; j++){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[j] + 1, dp[i]); 
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

发表于 2021-03-08 21:40:45 回复(0)

牛客341441072号

nums = list(map(int,input().split()))
l,r = 0,0
res = 1
for i in range(len(nums)-1):
    if nums[i+1]>nums[i]:
        r +=1
        res = max(res,r-l+1)
    else:
        r+=1
        l+=1
print(res)

发表于 2020-05-02 15:00:00 回复(0)