2501. longest square streak in an array

You are given an integer array nums. A subsequence of nums is called a square streak if:

• The length of the subsequence is at least 2, and
• after sorting the subsequence, each element (except the first element) is the square of the previous number.

Return the length of the longest square streak in nums, or return -1 if there is no square streak.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

solution

def longestSquareStreak(self, nums: List[int]) -> int:
	n = len(nums)
	nums.sort()
	  
	# dp[i] is longest valid subsequence ending at i
	dp = [1]*n
	  
	# next val in sequence, idx of prev val
	next_vals = {nums[0]**2: 0}
	  
	for i in range(1, len(nums)):
		if nums[i] in next_vals:
			dp[i] = max(dp[i], dp[next_vals[nums[i]]]+1)
		next_vals[nums[i]**2] = i
 
	best = max(dp)
	return best if best > 1 else -1