brute to better | 2 approach + optimization | sorting + constrain  (dp) | nlog(n) + n
Intuition\n Describe your first thoughts on how to solve this problem. \nproblem -> find subsequence in which after sorting values are square of previous.\n\nsu
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nproblem -> find subsequence in which after sorting values are square of previous.\n\nsubsequence => so order does not matter - a hint to sort\nsorting values => 2nd hint to sort the problem\ncondition => square so some maths is involved either sqrt or a*a used.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1st Approach - out of bound => thought of making state like dp[index][previous] after observing that 1e5 sqrt is 316.something so at max previous value can be 316 but still 1e5*(316) was out of bound.\n\n2nd Approach - sort given data, than traverse it and for every value if it\'s sqrt is present than we add length.\n\nsorting will be nlogn\nfinding sqrt is maths o(1)\nfinding sqrt in data is o(1) using len array to keep track and also maintain answer till that sqrt value.\n\noptimization - values can be from 2 to 1e5 it is hint in itself.\nAs we can have a array to store values occurance as 1 if present.\n\nThan we can build our answer on top of this occurance array as making a loop for 2 to 1e5 and for every value -\n1) if it is present in occurance array.\nif(occ[i]!=0)\n2) if it\'s sqrt is present in occurance array.\nocc[i] = 1 + occ[sqrt(i)]\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1st approach - n*(sqrt(maxvalue = 1e5))\n2nd approach - O(nlog(n) + n)\noptimization - O(1e5) - O(max value)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1st approach - O(1e5*(317)) // out of bound\n2nd approach - O(1e5) - O(max value)\noptimization - O(1e5) - O(max value)\n\n**open for discussion feel free to teach me :-)**\n# Code\n```cpp []\n\n#include <bits/stdc++.h>\nusing namespace std;\ntypedef long long ll;\ntypedef unsigned long long ull;\ntypedef long double lld;\n \n# define vi vector<int>\n# define vl vector<ll>\n# define vc vector<char>\n# define vvc vector<vector<char>>\n# define vvi vector<vector<int>>\n# define vvl vector<vector<ll>>\n# define pii pair<int,int>\n# define vpii vector<pii>\n# define vvpii vector<vector<pii>>\n \n#define ff first\n#define ss second\n#define yup cout<<"YES"<<endl;\n#define nope cout<<"NO"<<endl;\n#define pb push_back\n#define pp pop_back\n#define all(x) (x).begin(),(x).end()\n#define endl \'\\n\'\n#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);\n#define pout(x,e) cout<<fixed<<setprecision(e)<<x<<endl;\n#define FOR(i,s,e,j) for(int i=s; i<e; i+=j)\n#define sz(x) (x).size()\n \nclass Solution {\npublic:\n    // int dp[100000][317];\n    int n;\n\n    // int solve(vi& a, int ind, int prev){\n    //     if(prev>=317){\n    //         return 0;\n    //     }\n    //     if(ind>=n){return 0;}\n\n    //     // if(dp[ind][prev]!=-1){\n    //     //     return dp[ind][prev];\n    //     // }\n\n    //     int ans = solve(a, ind+1, prev);\n\n    //     if(prev==1 && a[ind]<400){\n    //         ans = max(ans, 1 + solve(a, ind+1, a[ind]));\n    //     }\n    //     else if(prev*prev == a[ind]){\n    //         ans = max(ans, 1 + solve(a, ind+1, a[ind]));\n    //     }\n\n\n    //     // return dp[ind][prev] = ans;\n    //     return ans;\n    // }\n\n    int longestSquareStreak(vector<int>& nums) {\n        sort(all(nums));\n\n        n = sz(nums);\n\n        // // memset(dp, -1, sizeof(dp));\n\n        // int len = solve(nums, 0, 1);\n\n        // if(len<=1){return -1;}\n        // return len;\n\n        int len[100001] = {0};\n \n        int ans = 0;\n        for(auto i:nums){\n            len[i]=1;\n            int sq = sqrt(i);\n            if((sq*sq == i) && len[sq]!=0){\n                len[i] = 1 + len[sq];\n                ans = max(ans, len[i]);\n            }\n        }\n\n        if(ans<=1){\n            return -1;\n        }\n        return ans;\n\n    }\n};\n```
['Array', 'Dynamic Programming', 'Recursion', 'Sorting', 'C++']