Freewheel 4.16笔试 第三题代码

package main

import (
	"fmt"
	"math"
)

func longestGeometricSeqLength(nums []int) int {
	// write code here
	if len(nums) == 0 {
		return 0
	}
	s1 := solution(nums)
	left, right := 0, len(nums)-1
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
	s2 := solution(nums)
	ans := s1
	if s2 > ans {
		ans = s2
	}
	if ans == math.MinInt64 {
		ans = 1
	}
	return ans
}

func solution(nums []int) int {
	n := len(nums)
	dp := make([]map[int]int, n)
	// dp:=make(map[int]map[int]int)  // 下标 - 比例 - 最长长度
	dp[0] = make(map[int]int)

	ans := math.MinInt64

	for i := 1; i < n; i++ {
		dp[i] = make(map[int]int)
		for j := i - 1; j >= 0; j-- {
			if nums[j] != 0 && nums[i]%nums[j] == 0 {
				vv := nums[i] / nums[j]
				preLength, ok := dp[j][vv]
				//fmt.Println(preLength, ok)
				newLength := 0
				if !ok {
					newLength = 2
				} else {
					newLength = preLength + 1
				}
				if curLength, ok := dp[i][vv]; !ok {
					dp[i][vv] = newLength
				} else if newLength > curLength {
					dp[i][vv] = newLength
				}
				if dp[i][vv] > ans {
					ans = dp[i][vv]
				}
			}
		}
		//fmt.Println(i, dp[i])
	}

	return ans
}

func main() {
	ans := longestGeometricSeqLength([]int{2, 3})
	fmt.Println(ans)
}