C++ 解法, 执行用时: 3ms, 内存消耗: 320KB, 提交时间: 2022-03-13

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

void handler(vector<int>& nums, int n){
    vector<int> dp(n+1,1);
    int ans = INT_MIN;
    for(int i = 1; i <= n; ++i){
        int maxNum = INT_MIN;
        for(int j = 1; j < i; ++j){
            if(nums[i-1]>nums[j-1]){
                maxNum = maxNum<dp[j] ? dp[j] : maxNum;
            }
        }
        if(maxNum!=INT_MIN)
            dp[i] = maxNum + 1;
        ans = ans<dp[i] ? dp[i] : ans;
    }
    cout<<ans<<endl;
}

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

C 解法, 执行用时: 3ms, 内存消耗: 324KB, 提交时间: 2022-06-17

#include <stdio.h>

int main() {
    int n, i = 0;
    scanf("%d", &n);
    
    int *num = (int *)malloc(sizeof(int) * n);
    while(i < n) {
        scanf("%d", num+i);
        i++;
    }
    
    int *minArray = (int *)malloc(sizeof(int) * n);
    int minLen = 0, lastRight, left, right, mid;
    
    i = 0;
    while(i < n) {
        if (minLen == 0 || (minLen > 0 && num[i] > minArray[minLen - 1])) {
            minArray[minLen++] = num[i];
        } else {
            left = 0;
            right = minLen - 1;
            lastRight = minLen;
            while(left <= right) {
                mid = (left + right) / 2;
                if (minArray[mid] >= num[i]) {
                    lastRight = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            
            minArray[lastRight] = num[i];
        }
        
        i++;
    }

    free(minArray);
    free(num);
    printf("%d", minLen);
    
    return 0;
}

C 解法, 执行用时: 3ms, 内存消耗: 328KB, 提交时间: 2022-08-01

#include<stdio.h>
#include<stdlib.h>
int fmax(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int n=0;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);
    int*dp=(int*)calloc(n,4);
    dp[0]=1;
    int len=0;
    for(int i=1;i<n;i++)
    {
        int max=0;
        for(int j=0;j<i;j++)
        {
            if(arr[i]>arr[j])
                max=fmax(max,dp[j]);
        }
        dp[i]=max+1;
    }
    int max=1;
    for(int i=0;i<n;i++)
        max=fmax(max,dp[i]);
    printf("%d",max);
    return 0;
}    

C 解法, 执行用时: 3ms, 内存消耗: 340KB, 提交时间: 2022-05-11

#include<stdio.h>
int n,a[1001],b[1001];
int find();
int max(int a,int b);
int main()
{
    int i;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    int c=find();
    printf("%d",c);
    return 0;
}
int find()
{
    if(n==0)
        return 0;
    int i,j;
    for(i=0;i<n;i++)
        b[i]=1;
    for(i=1;i<n;i++)
    {
        for(j=0;j<i;j++)
        {
            if(a[i]>a[j])
                b[i]=max(b[i],b[j]+1);
        }
    }
    int res=b[0];
    for(i=1;i<n;i++)
    {
        res=max(res,b[i]);
    }
    return res;
}
int max(int a,int b)
{
    if(a<b)
        return b;
    else
        return a;
}

C 解法, 执行用时: 3ms, 内存消耗: 340KB, 提交时间: 2022-04-07

#include <stdio.h>

int main()
{
    int n;
    scanf("%d",&n);
    int rem[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&rem[i]);
    }
    int dp[n];
    for(int i=0;i<n;i++)
    {
       dp[i]=1;
    }
    for(int i=1;i<n;i++)
    for(int j=0;j<=i;j++)
    {
        if(rem[i]>rem[j])
            dp[i]=dp[i]>dp[j]+1?dp[i]:dp[j]+1;
    }
    int max=1;
    for(int i=0;i<n;i++)
    {
        if(max<dp[i])
            max=dp[i];
    }
    printf("%d",max);
    return 0;
}