O(N logN) DP + Sorting Solution (C++ code, beats 95%)
Intuition\nMy first observation was that the order of the numbers in the array doesn\'t matter, since the subsequences are sorted anyways, so we can sort the ar
# Intuition\nMy first observation was that the order of the numbers in the array doesn\'t matter, since the subsequences are sorted anyways, so we can sort the array however we like.\nAfter we sort the array, all subsequences will be ordered correctly, for example: [**2**, 3, **4**, 6, 8, **16**].\nSo for each number, we can check if it\'s square exists after it in the array and if it does, we should always add it to our sequence.\nAlso another observation is that duplicates don\'t matter, for example if we had two values of 16 in the previous array, it\'s irrelevant which of the two we add to the subsequence.\n\n# Approach\n\nWe have established that for each number, we only need to check if it\'s square exists after it in the array, and duplicates don\'t matter, so it makes the most sense to store this result for every value.\nSince our values are all less than $10^5$, we can use a simple array to store this data. If we had bigger values, we would\'ve needed a hashmap or a similar container structure.\nSo for our dynamic programming we have the following recurrence:\n```\ndp[i] = length of the maximum subsequence that starts with the value i\ndp[i] = 1 + dp[i * i], if (i * i  exists in the array)\n\t  = 1            , otherwise\n```\nSince $dp[i]$ depends on $dp[i \\cdot i]$, which is always greater, it makes sense to sort the numbers non-increasingly (reverse order), to process the bigger numbers first and for every element $a$ in the array, we already know $dp[a \\cdot a]$.\n\n\n# Complexity\n- Time complexity: $O(n * log(n))$ because of sorting\n\n- Space complexity: \n\t- $O(max\\_value)$ in this approach\n\t- $O(n)$ for the hashmap approach\n\n# Code\n```cpp []\n#include <algorithm>\n#include <vector>\n#include <cstring>\n\nconst int VMAX = 1e5 + 8;\n\nint dp[VMAX];\n\nclass Solution {\n  public:\n\tint longestSquareStreak(std::vector<int> &nums)\n\t{\n\t\t// sort in reverse order\n\t\tstd::sort(nums.begin(), nums.end(), std::greater<int>());\n\n\t\t// initialise the dp with zeroes for all values\n\t\tint max = nums[0];\n\t\tmemset(dp, 0, sizeof(int) * (1 + max));\n\n\t\tint ans = 0;\n\t\tfor (int i : nums) {\n\t\t\t// base case is that we can\'t extend the subsequence \n\t\t\tdp[i] = 1;\n\n\t\t\t// check if i * i doesn\'t overflow\n\t\t\t// and if dp[i * i] > 0\n\t\t\t// (ie. i * i exists before the current val)\n\t\t\tif (i <= max / i && dp[i * i] != 0) {\n\t\t\t\tdp[i] = 1 + dp[i * i];\n\t\t\t}\n\n\t\t\t// if we extended the subsequence more than prev. answer\n\t\t\t// update the answer\n\t\t\tif (dp[i] > ans) {\n\t\t\t\tans = dp[i];\n\t\t\t}\n\t\t}\n\n\t\t// if ans is < 2, we have no valid subsequence, so return -1\n\t\tif (ans < 2) {\n\t\t\tans = -1;\n\t\t}\n\t\treturn ans;\n\t}\n};\n```
['Array', 'Dynamic Programming', 'Sorting', 'C++']