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

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    
    int *nums = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    
    int ascArray[1000], dscArray[1000], ascLen = 0, dscLen = 0;
    
    if (n == 1) {
        ascLen = 1;
        dscLen = 1;
    } else {
        int v, left, right, mid, lastRight;
        for (int i = 0; i < n; i++) {
            v = nums[i];
            
            lastRight = ascLen;
            left = 0;
            right = ascLen - 1;
            while(left <= right) {
                mid = (left + right) / 2;
                if (ascArray[mid] >= v) {
                    lastRight = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            ascArray[lastRight] = v;
            if (lastRight == ascLen) {
                ascLen++;
            }
            
            lastRight = dscLen;
            left = 0;
            right = dscLen - 1;
            while(left <= right) {
                mid = (left + right) / 2;
                if (dscArray[mid] < v) {
                    lastRight = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            dscArray[lastRight] = v;
            if (lastRight == dscLen) {
                dscLen++;
            }
        }
    }
    
    printf("%d\n%d", dscLen, ascLen);
    
    free(nums);
    
    return 0;
}

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

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    
    int *height = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &height[i]);
    //    printf("%d ",height[i]);
    }
   //  printf("\n***");
    int ascending[1000], descending[1000], asc_Length = 0, des_Length = 0;
    
    if (n == 1) {
        asc_Length = 1;
        des_Length = 1;
    } else {
        int temp, left_positon, right_position, mid_position, last_right_position;
        for (int i = 0; i < n; i++) {
            temp = height[i];
            
            last_right_position = asc_Length;
            left_positon = 0;
            right_position = asc_Length - 1;
            while(left_positon <= right_position) {
                mid_position = (left_positon + right_position) / 2;
                if (ascending[mid_position] >= temp) {
                    last_right_position = mid_position;
                    right_position = mid_position- 1;
                } else {
                    left_positon = mid_position + 1;
                }
            }
            ascending[last_right_position] = temp;
            if (last_right_position == asc_Length) {
                asc_Length++;
            }
            
            last_right_position = des_Length;
            left_positon = 0;
            right_position = des_Length - 1;
            while(left_positon <= right_position) {
                mid_position = (left_positon + right_position) / 2;
                if (descending[mid_position] < temp) {
                    last_right_position = mid_position;
                    right_position = mid_position - 1;
                } else {
                    left_positon = mid_position + 1;
                }
            }
            descending[last_right_position] = temp;
            if (last_right_position == des_Length) {
                des_Length++;
            }
        }
    }
   
    printf("%d\n%d", des_Length, asc_Length);
   
    free(height);
    
    return 0;
}

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

#include <stdio.h>
int getmax(int a, int b){
    return a > b ? a : b;
}
int getmin(int a, int b){
    return a > b ? b : a;
}
int main(){
    int n;
    scanf("%d",&n);
    int* num = (int*)malloc(n*sizeof(int));
    int* dp1 = (int*)malloc(n*sizeof(int));
    int* dp2 = (int*)malloc(n*sizeof(int));
    int i,j;
    for(i = 0;i < n; i++){
        scanf("%d",&num[i]);
        dp1[i] = 1;
        dp2[i] = 1;
    }
    int max = 0;
    int max1 = 0;
    for(i = 0; i < n;i++){
        max = 0;
        max1 = 0;
        for( j = 0; j < i;j++){
            if(num[i] <= num[j]){
                max = getmax(max,dp1[j]);   
            }
            if(num[i] > num[j]){
                max1 = getmax(max1,dp2[j]);   
            }
        }
        dp1[i] = max + 1;
        dp2[i] = max1 + 1;
    }
    for(i = 0;i < n; i++){
//         printf("%d %d\n",dp1[i],dp2[i]);
        if(max < dp1[i]){
            max = dp1[i];
        }
        if(max1 < dp2[i]){
            max1 = dp2[i];
        }
    }
    printf("%d\n",max);
    printf("%d",max1);
    return 0;
}

C 解法, 执行用时: 4ms, 内存消耗: 320KB, 提交时间: 2022-07-02

#include <stdio.h>

int main(){
    int n = 0;
    scanf("%d",&n);
    int arr[n];
    int dp[n];
    int dp1[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&arr[i]);
        dp[i] = 1;
        dp1[i] = 1;
    }
    int i = 0;
    int j = 0;
    int sign = 0;
    int sign1 = 0;
    for(i = 1; i < n; i++){
        for(j = 0; j < i; j++){
            if(arr[i] <= arr[j]){
                sign = 1;
                dp[i] = dp[i] > dp[j] ? dp[i] : dp[j];
            }
            if(arr[i] > arr[j]){
                sign1 = 1;
                dp1[i] = dp1[i] > dp1[j] ? dp1[i] : dp1[j];
            }
        }
        if(sign == 1){
            dp[i] += 1;
            sign = 0;
        }
        if(sign1 == 1){
            dp1[i] += 1;
            sign1 = 0;
        }
    }
    int tmp = 0;
    int tmp1 = 0;
    for(int i = 0; i < n; i++){
        tmp = tmp > dp[i] ? tmp : dp[i];
        tmp1 = tmp1 > dp1[i] ? tmp1 : dp1[i];
    }
    printf("%d\n",tmp);
    printf("%d",tmp1);
    return 0;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 388KB, 提交时间: 2022-08-06

#include<iostream>
#include<cstring>
using namespace std;
int binSearch(int *nums,int r,int value)
{
    int l=0;
    while(l<r)
    {
        int mid=l+((r-l)>>1);
        if(nums[mid]<=value)
            l=mid+1;
        else
            r=mid;
    }
    if(nums[r-1]==value)
        return r-1;
    return r;
}
int supper_bound(int *nums,int r,int value)
{
    int l=0;
    while(l<r)
    {
        int mid=l+((r-l)>>1);
        if(nums[mid]>=value)
            l=mid+1;
        else
            r=mid;
    }
    return r;
}
int func(int *nums,int n)
{
    int top=0;
    int arr[n];
    arr[0]=nums[0];
    for(int i=1;i<n;++i)
    {
        if(nums[i]>arr[top])
            arr[++top]=nums[i];
        else{
            int index=binSearch(arr, top, nums[i]);
            arr[index]=nums[i];
        }
    }
    return top+1;
}
int func2(int *nums,int n)
{
    int top=0;
    int arr[n];
    arr[0]=nums[0];
    for(int i=1;i<n;++i)
    {
        if(nums[i]<=arr[top])
            arr[++top]=nums[i];
        else{
            int index=supper_bound(arr, top, nums[i]);
            arr[index]=nums[i];
        }
    }
    return top+1;
}

int main()
{
    int n;
    cin>>n;
    int nums[n];
    for(int i=0;i<n;++i)
    {
        cin>>nums[i];
    }
    cout<<func2(nums,n)<<endl;
    cout<<func(nums,n);
    return 0;
}