首页 > 试题广场 >

最长递增子序列(LCS)

[编程题]最长递增子序列(LCS)
  • 热度指数:315 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
给定一个序列 An = a1 ,a2 ,  ... , an ,找出最长的子序列使得对所有 i < j ,ai < aj 。求出这个子序列的长度

输入描述:
输入的序列


输出描述:
最长递增子序列的长度
示例1

输入

1 -1 2 -2 3 -3 4

输出

4
#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)
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)
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)