#include <stdio.h>

int num[1001];
int dp_long[1001];
int dp_short[1001];

int max(int a,int b) {
    return a>b? a:b;
}

int bottom_up(int n) {
    int res=0;
    for(int i=1; i<=n; i++) {
        dp_long[i]=1;
        for(int j=1; j<=i-1; j++) {
            //증가하는 부분 가장 큰값보다 왼쪽
            if(num[i]>num[j]) dp_long[i]=max(dp_long[i],dp_long[j]+1);
        }
    }
    for(int i=n; i>=1; i--) {
        dp_short[i]=1;
        //감소하는부분
        for(int j=n; j>=i+1; j--) {
            if(num[i]>num[j]) dp_short[i]=max(dp_short[i],dp_short[j]+1);
        }
    }
    for(int i=1; i<=n; i++) {
        res=max(dp_long[i]+dp_short[i]-1,res);
    }
    return res;
}

int main() {
     int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
        scanf("%d",&num[i]);
    }
    printf("%d",bottom_up(n));
    return 0;
}

Embed on website

To embed this project on your website, copy the following code and paste it into your website's HTML: