首页 > 试题广场 >

最长上升子序列(一)

[编程题]最长上升子序列(一)

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

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标 $i$ 和 $j$ 满足 $i<j$ 且 $arr_i \geq arr_j$ 。

数据范围： $0\leq n \leq 1000$ , $|arr_i| \le 10^9 \$

要求：时间复杂度 $O(nlogn)$ ，空间复杂度 $O(n)$

输入描述:

第一行输入一个正整数 n ，表示数组的长度 
第二行输入 n 个整数表示数组的每个元素。

输出描述:

输出最长严格上升子序列的长度

示例1

输入

7
6 3 1 5 2 3 7

输出

说明

该数组最长上升子序列为 [1,2,3,7] ，长度为4

算法知识视频讲解

C++

Spectre_

#include <iostream>
using namespace std;

int main() {
    int n, res = 1;
    cin >> n;
    int arr[n], dp[n];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        dp[i] = 1;
    }
    // 时间复杂度O(N^2)，空间复杂度O(N)
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[j] < arr[i]) dp[i] = max(dp[j] + 1, dp[i]);
        }
        res = res > dp[i] ? res : dp[i];
    }
    cout << res;
    return 0;
}

发表于 2022-11-01 14:53:15 回复(0)

C++

土泥豆

#include<iostream>
#include<vector>
#include<limits.h>
using namespace std;
//dp[i]：以a[i]结尾的最长上升子序列
//动态方程：dp[i]=max(dp[i],dp[j]+1)
int main(){
    int n,summax=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    vector<int> dp(n,1);
    for(int i=1;i<n;i++)
        for(int j=0;j<i;j++)
            if(a[i]>a[j])
            {
                dp[i]=max(dp[i],dp[j]+1);
                summax=max(summax,dp[i]);
            }
    cout<<summax;
}

发表于 2022-08-10 23:18:08 回复(0)

C++

牛客288355985号

nlog(n)解法实现

#include<iostream>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;

int main(){
  int n,a,h[1009];
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    h[i]=INF;
    *lower_bound(h, h+i, a)=a;
  }
  cout<<lower_bound(h, h+n, INF)-h<<endl;
}

发表于 2022-08-28 15:35:33 回复(0)

Python3

liangzhengjie

import sys

def main():
    num = int(sys.stdin.readline().strip())
    arr = list(map(int, sys.stdin.readline().strip().split(' ')))

    dp = [1 for i in range(num)]
    for i in range(num):
        for j in range(i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    res = max(dp)

    # print(dp)
    print(res)

main()

编辑于 2024-02-28 21:11:11 回复(0)

努力学好算法的小白

import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int length = in.nextInt();
        int[] nums = new int[length];
        for(int i = 0;i<length;i++){
            nums[i] = in.nextInt();
        }
        int result = GetMaxLongLength(nums);
        System.out.print(result);

    }
    public static int GetMaxLongLength(int[] nums){
        //确定dp数组
        int[] dp = new int[nums.length+1];
        //全部填补为1
        Arrays.fill(dp,1);
        //很显然dp[0] =1
        for(int i = 1;i<nums.length;i++){
            for(int j = 0;j<i;j++){
                if(nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }

        int result = 0;
        for(int k = 0;k<dp.length;k++){
            result = Math.max(result,dp[k]);
        }

        return result;
    }
}

发表于 2023-02-28 12:46:48 回复(0)

小谷围做题家

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void async function () {
    let n=parseInt(await readline());
    let arr=(await readline()).split(" ").map(it=>parseInt(it));
    let dp=new Array(n).fill(1),max=1;
    for(let i=1;i<n;i++){
        let ans=dp[i];
        for(let j=i-1;j>=0;j--){
            if(arr[i]>arr[j]&&dp[j]+1>ans) ans=dp[j]+1;
        }
        dp[i]=ans;
        if(ans>max) max=ans;
    }
    console.log(max);
}()

发表于 2022-12-10 10:53:43 回复(0)

C++

向秋招冲刺！

#include <iostream>
#include <vector>
using namespace std;
int dp[10001];

int main() {
    int n;
    cin >> n;
    vector<int> arr(n + 1);
    for(int i = 0; i < n; ++ i)
      cin >> arr[i];
    dp[0] = 1;
    int res = 0;
    for(int i = 1; i < n; ++ i){
        int tmp = 0;
        for(int j = 0; j < i; ++ j){
           if(arr[i] > arr[j])
             tmp = max(tmp,dp[j]);
        }
        dp[i] = tmp + 1;
        res = max(res,dp[i]);
    }
    cout << res;
    return 0;
}

发表于 2022-10-11 10:47:15 回复(0)

Python 3

Kiron_L

def solution(arr, n):
    dp = [1] * n
    res = 0
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i], dp[j] + 1)
                res = max(res, dp[i])
    return res


n = int(input())
arr = list(map(int, input().split()))
print(solution(arr, n))

发表于 2022-08-17 23:01:46 回复(0)

Java

ByteWong.

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] nums = new int[n];
            for(int i=0;i<n;i++) {
                nums[i] = in.nextInt();
            }
            // 2 4 5 6 3 4 7
            // dp[i][j] = 3
            
            int[] dp = new int[n+1];
            dp[1] = 1;
            int max = 0;
            for(int i=2;i<=n;i++) {
                dp[i] = 1;
                for(int j=1;j<i;j++) {
                    if(nums[i-1] > nums[j-1]) {
                        dp[i] = Math.max(dp[j]+1,dp[i]);
                    }
                }
                max = Math.max(max,dp[i]);
            }
            System.out.println(max);
        }
    }
}

发表于 2022-04-30 15:06:18 回复(0)

cheerful0120

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=sc.nextInt();
        }
        int res=-1;
        int[] dp=new int[n+1];
        Arrays.fill(dp,1);
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(arr[j]>arr[i]){
                    dp[j]=Math.max(dp[j],dp[i]+1);
                }
            }
            res=Math.max(dp[i],res);
        }
        System.out.println(res);
    }
}

发表于 2022-04-12 15:46:48 回复(0)

C++

元气少女李逵

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int b;
    vector<int> a;
    for(int i=0;i<n;i++)
    {
        cin>>b;
        a.push_back(b);
    }
    vector<int> dp(n+1,1);
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(a[j]>a[i])
            {
                dp[j]=max(dp[j],dp[i]+1);
            }
        }
        
    }
    sort(dp.begin(),dp.end(),greater<int>());
    cout<<dp[0]<<endl;
    return 0;

}

发表于 2022-04-11 10:34:23 回复(0)

C++

等一个offer！

#include<bits/stdc++.h>
using namespace std;

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

int main(){
    int n;cin>>n;
    vector<int>nums(n);
    for(int i=0;i<n;i++) cin>>nums[i];
    cout<<LengthOfLTS(nums);
}

发表于 2022-03-31 22:15:08 回复(0)

Javascript

牛客265408372号

1 6 4 7 5 3 2 7

rl.on('line', function (line) {
const tokens = line.trim();
num.push(tokens);
if (num.length === 2) {
var numStr = num[1].split(' ');
let len = numStr.length;
let dp = new Array(len).fill(1);
let max = 0;
let tem = 0;
for(let i=1; i<len; i++) {
tem = 0;
for(let j=0; j<i; j++){
if(numStr[i] > numStr[j]){
tem = dp[j] >= tem ? dp[j] : tem;
}
}
dp[i] = dp[i] + tem;
max = dp[i] >= max ? dp[i] : max
}
console.log(max)
}
});

预期输出 3

实际输出 4

谁有问题？

发表于 2022-03-28 23:16:27 回复(0)

Python 3

.黑色.

def func(n, arr):
    
    if n <= 1: return n
    
    ans = 0
    dp = [arr[0]]
    for idx in range(1, n):
        num = arr[idx]
        if num > dp[-1]:
            dp.append(num)
        elif num == dp[-1]: continue
        else:
            l, r = 0, len(dp) - 1
            while l <= r:
                m = l + ((r - l) >> 1)
                if dp[m] > num:
                    r = m -1
                else:
                    l = m + 1
            dp[l] = num
        ans = max(ans, len(dp))
    return ans

发表于 2022-03-27 17:11:43 回复(0)

C++

kuro_nyg

//贪心二分，不知道为啥用lower_bound在数据特别大时样例过不了

#include <bits/stdc++.h>

using namespace std;
int a[1100],low[1100];
int bound(int a[],int r,int x){
    int l=1,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(a[mid]<=x)
        l=mid+1;
        else
        r=mid-1;
    }
    return l;
}
int main(int argc, char** argv) {
int i,j,n,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",a+i),low[i]=0x7fffffff;
    low[1]=a[1];
    ans=1;
    for(i=2;i<=n;i++){
        if(a[i]>low[ans])
        low[++ans]=a[i];
        else{
            low[bound(low,ans,a[i])]=a[i];
        }
    }
    cout<<ans;
    return 0;
}

发表于 2022-03-14 22:10:43 回复(0)

C++

wydxry

#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5;
int a[N],dp[N];
int n;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) dp[i]=1;
    int ans=0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(a[j]>a[i]){
                dp[j]=max(dp[j],dp[i]+1);
                ans=max(ans,dp[j]);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表于 2022-03-03 23:23:51 回复(0)