MyHearthFlutter

#include<stdio.h>
int n;
int arr[3010];
int max(int a,int b){
    return (a > b ? a : b);
}
int dp[3010][2];
int cal(int index,int state){
    int maxa = 1;
    if(dp[index][state])return dp[index][state];
    for(int i=index+1;i<=n;i++){
        if(state == 1 && arr[i] < arr[index])
            maxa = max(maxa,cal(i,0) + 1);
        else if(state == 0 && arr[i] > arr[index])
            maxa = max(maxa,cal(i,1) + 1);
    }
    return dp[index][state] = maxa;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    printf("%d",max(cal(1,1),cal(1,0)));
    return 0;
}