Java 解法, 执行用时: 162ms, 内存消耗: 20216K, 提交时间: 2022-02-27 11:57:44

import java.util.Scanner;

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();
        }
        System.out.println(LIS(arr,n));
    }
    public static int LIS(int [] arr,int n){
        int p;
        int len = 1;
        int [] arr1 = new int[n];
        arr1[0] = arr[0];
        for (int i = 1; i < n; i++) {
            if (arr[i]>arr1[len-1]){
                arr1[len++] = arr[i];
            }else {
                p = search(arr1,arr[i],0,len-1);
                arr1[p] = arr[i];
            }
        }
        return len;
    }

    private static int search(int[] arr1, int x, int l, int r) {
        while (l<r){
            int mid = l+(r-l)/2;
            if (arr1[mid]>=x){
                r =mid;
            }else {
                l=mid+1;
            }
        }
        return l;
    }
}

C++(clang++11) 解法, 执行用时: 36ms, 内存消耗: 432K, 提交时间: 2021-04-24 09:18:23

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