一. 题目

二. 思路

三. 代码

const int N=1e5+10;
const double EPS=1e-8;

class DP
{
public:
    int f[N];

public:
    void init(vector<int>& nums)
    {
        fill(f, f+N, -1);
        for(auto &it:nums) f[it]=1;
        sort(nums.begin(), nums.end());
    }

    bool isEqual(double v1, int v2)
    {
        if(fabs(v1-v2)<EPS)
            return true;
        return false;
    }

    int work(vector<int>& nums)
    {
        init(nums);//初始化
        for(auto &it:nums)
        {
            double v1=sqrt(it);
            int v2=(int)v1;
            if(!isEqual(v1, v2)||f[v2]==-1) continue;
            f[it]=max(f[it], f[v2]+1);
        }
                                        //+1才到尾后下标
        return reduce(f, f+nums.back()+1, -1, [](const int &current_maxv, const int &v)->int{
            if(v==-1||v==1) return current_maxv;//当f不为1或-1时为有效值
            return max(current_maxv, v);
        });
    }
}dp;

class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        return dp.work(nums);
    }
};