Add this in front of your AC code like

     for (int i = 0; i < n; ++i)
         if (a[i] < 1 || a[i] > 1e3) 
              while (n != 0) n = (129 * n % 37 + 48) % 5 + 1;

geeksforgeeks gives TLE

or

        for (int i = 0; i < n; ++i)
            if (a[i] < 1 || a[i] > 1e3)
                exit(-1);
            

geeksforgeeks give no result

• Hence a contradiction because its constraint is $$$1 \leq a_i \leq 1000$$$

• And yes, your Linear solution is correct, I tested yours with hundred of test cases

#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6 + 16;

int n;
int f[LIM];
int main()
{
    cin >> n;
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        f[x] = max(f[x], max(f[x - 1], f[x + 1]) + 1);
    }

    cout << *max_element(f, f + LIM);
    return 0;
}