#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;
}
To embed this project on your website, copy the following code and paste it into your website's HTML: