SPOJ LIS

LIS.cpp

    #include <bits/stdc++.h>
    using namespace std;
     
    #define FOR(i, a, b) for(int i = a; i <= b; i++)
    #define FORD(i, a, b) for(int i = a; i <  b; i++)
    #define REP(i, a, b) for(int i = a; i >= b; i--)
    #define REPD(i, a, b) for(int i = a; i >  b; i--)

    #define DEBUG(x) { cout << #x << " = " << x << endl; }
    #define sqr(x) ((x) *(x))
     
    #define ull unsigned long long
    #define ll long long

    // __gcd algorithm
    ll gcd(ll a, ll b) {
        return b ? gcd(b, a%b) : a; 
    }
    // end __gcd

    // power modulo algorithm
    ll power_modulo(ll a, ll base, ll mod) {
        if(!base) { return 1; }
        ll temp = power_modulo(a, base / 2, mod);
        if(base & 1) return a * sqr(temp) % mod;
        return sqr(temp) % mod;
    }
    // end power modulo
    
    // int_To_String algorithm
    string int_To_String(int i)
    {
        stringstream ss;
        ss << i;
        return ss.str();
    }
    // end int_To_String algorithm

    // string_To_int algorithm
    int string_To_int(string s) {
        return atoi(s.c_str());
    }
    // end string_To_int algorithm

    // KMP algorithm
    int KMP(string s, string t) {
        int n = s.length(), m = t.length();
        int* pit = new int[m+1];
        if(m >= 0) pit[0] = 0;
        if(m >= 1) pit[1] = 0;
        FOR(i, 2, m) {
            for(int j = pit[i-1]; ;j = pit[j]) {
                if(t[j] == t[i-1]) { pit[i] = j + 1; break; }
                if(j == 0) { pit[i] = 0; break; }
            }
        }
        for(int i = 0, j = 0; i < n; ) {
            if(s[i] == t[j]) {
                i++; j++;
                if(j == m) return i - m;
            } else if(j > 0) {
                j = pit[j];
            } else i++;
        } delete[] pit;
        return -1;
    }
    // end KMP algorith

    // Z algorithm
    int* Z(string s) {
        int n = s.size();
        int* z = new int[n+1];
        int l = 0, r = 0;
        z[0] = n;
        FOR(i,1,n) {
            z[i] = 0;
            if(i > r) {
                l = r = i;
                while(r < n && s[r - l] == s[r]) r++;
                z[i] = r - l; 
                r--;
            } else if(z[i - l] < r - i + 1) z[i] = z[i - l];
            else {
                l = i;
                while(r < n && s[r - l] == s[r]) r++;
                z[i] = r - l;
                r--;
            }
        }
        return z;
    }
    // end Z algorithm

    // Binary Search algorithm
    bool binSearch(int A[], int N, int var) {
        int Left = 1, Right = N, Mid;
        while(Left <= Right) {
            Mid = (Left + Right) >> 1;
            if(A[Mid] == var) return true;
            else if(var > A[Mid]) Left = Mid + 1;
            else Right = Mid - 1;
        }
        return false;
    }

    int N, A[10005];
    int maxx = 0;

    bool check_Nghiem(int x) {
        int delta = 1 + 8*x;
        int sqrt_del = sqrt(delta);
        if(sqr(sqrt_del) == delta && (-1 + sqrt_del) % 2 == 0 && (-1 + sqrt_del) != 0) return true;
        return false;
    }

    int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        // solution starts...

        cin >> N;
        FOR(i,1,N) cin >> A[i];
        int ans = 0,  cnt;

        for(int i = 1; i <= N; ) {
            if(check_Nghiem(A[i])) {
                cnt = 0;
                while(i <= N && check_Nghiem(A[i])) {
                    cnt++;
                    if(i == N || A[i+1] < A[i]) {
                        i++;
                        break;
                    }
                    i++;
                }
                ans = max(cnt, ans);
            } else i++;
        }

        cout << ans << endl;

        // solution end...
        return 0;
    }