//BAEKJOON 11054
#include <stdio.h>

int N, arr[1010], dt[1010][2], len;

int f(int n, int st) { //st==0 : st==1 : 
 
    if(dt[n][st]!=-1) 
        return dt[n][st];
    else { 
        int max=1;
        if(st==0) { 
            for(int i=1; i<n; i++) { 
                if(arr[i]<arr[n]) { 
                    int tmp=f(i, 0)+1; 
                    if(max<tmp) max=tmp; 
                }  
            } 
        } 
        else { 
            for(int i=n+1; i<=N; i++) {
                if(arr[i]<arr[n]) {
                    int tmp=f(i, 1)+1; 
                    if(max<tmp) max=tmp; 
                }  
            } 
        }
        return dt[n][st]=max;
    }
}

int main() {

    scanf("%d", &N);

    for(int i=1; i<=N; i++) {
        dt[i][0]=dt[i][1]=-1;
        scanf("%d", &arr[i]);
    }

    for(int i=1; i<=N; i++) {
        //printf("%d : %d %d\n", i , f(i, 0), f(i, 1));
        int len_tmp=f(i,0)+f(i,1)-1;
        if(len<len_tmp) len=len_tmp;
    }
    printf("%d", len);
}

Embed on website

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