OJ Board

Code: Select all

Removed After AC

Code: Select all

1
10
3
8
1
5
10
4
9
2
7
6

Code: Select all

#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){

    int cases, e;
    scanf("%d",&cases);
    for(e=0; e<cases; e++){

        int n, i;
        scanf("%d",&n);




        int arr[n];

        for(i=0; i<n; i++){
            scanf("%d",&arr[i]);
        }

        int best = 0;
        int k;
        for(k=0; k<n; k++){
            // Get longest decreasing sequence for bot


            vector<int> top;
            vector<int> bot;

            int z;
            for(z=k; z<n;z++){
                if(z>k){
                    if(arr[z] < arr[k]){
                        bot.push_back(arr[z]);
                    } else {
                        top.push_back(arr[z]);
                    }
                }
            }

            // Print stuff
            //printf("Starting at %d\n",arr[k]);
            int t;
            //printf("Dec:\n");
            //for(t=0; t<bot.size(); t++)
            //    printf("%d ",bot[t]);
           // printf("\nInc:\n");
            //for(t=0; t<top.size(); t++)
            //    printf("%d ",top[t]);
           // printf("\n");


            int bot_size = bot.size();

            int bot_dp[bot_size];

            int bot_maxi = 0;
            int bot_maxlen = 0;

            for(i=k; i<bot_size; i++){
                bot_dp[i] = 1;
                int j;
                for(j=k; j<i; j++){
                    if(bot[j] > bot[i] && bot_dp[j] + 1 > bot_dp[i]){
                        bot_dp[i] = bot_dp[j] + 1;
                    }

                    if(bot_dp[i] > bot_maxlen){
                        bot_maxlen = bot_dp[i];
                        bot_maxi = i;
                    }
                }
            }

            //printf("Longest for decreasing is %d\n", bot_maxlen);

            // Get longest increasing sequence for inc

            int top_size = top.size();

            int top_dp[top_size];

            int top_maxi = 0;
            int top_maxlen = 0;

            for(i=k; i<top_size; i++){
                top_dp[i] = 1;
                int j;
                for(j=k; j<i; j++){
                    if(top[i] > top[j] && top_dp[j] + 1 > top_dp[i]){
                        top_dp[i] = top_dp[j] + 1;
                    }

                    if(top_dp[i] > top_maxlen){
                        top_maxlen = top_dp[i];
                        top_maxi = i;
                    }
                }
            }

            //printf("Longest for increasing is %d\n", top_maxlen);

            // Remeber to add the starting cart in the sequence

            if(1+top_maxlen+bot_maxlen > best){
                best = 1+top_maxlen+bot_maxlen;
            }
        }
        printf("%d\n",best);
    }


    return 0;
}