# 2501. Longest Square Streak in an Array
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Longest Increasing Subsequence`
Link: https://leetcode.com/problems/longest-square-streak-in-an-array/description/
## 思路
思路参考[这里](https://leetcode.com/problems/longest-square-streak-in-an-array/solutions/2899678/short-dp-c-java-lis-type/)
先排序然后参考LIS的思路
对于每个数字来说 如果是平方数 并且它的root square之前出现过 那么这个数在map里对应的val就是root在map里对应的val+1
## Code

class Solution {
    public int longestSquareStreak(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        Arrays.sort(nums);
        int res = 0;
        for(int i=0; i<nums.length; i++){
            int root = (int)Math.sqrt(nums[i]);
            if(root*root == nums[i]) map.put(nums[i], map.getOrDefault(root, 0)+1);
            else map.put(nums[i], 1);
            res = Math.max(map.get(nums[i]), res);
        }
        return res<2?-1:res;
    }
}