欢迎您访问 最编程 本站为您分享编程语言代码,编程技术文章!
您现在的位置是: 首页

leetcode 1027 最长同构数列 思考的问题

最编程 2024-10-14 07:14:45
...

https://leetcode.cn/problems/longest-arithmetic-subsequence/

在这里插入图片描述
如果序列是:3 0 3,枚举的公差是3
对于第一个数3,它的序列长度就是他自己3
对于第二个数0,它的序列长度就行它自己0
对于第三个数,它的序列长度应该是【0,3】长度为2,第一个数也是3

一个数出现的位置越靠后,则能构成的等差数列的长度就有可能会越长

class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        min_t = nums[0]
        max_t = nums[0]
        # 最大公差
        max_cha = -1
        # 最小公差
        min_cha = 1000
        ll = len(nums)
        for i in range(1,ll):
            min_cha = min(nums[i]-max_t, min_cha)
            max_cha = max(nums[i]-min_t, max_cha)
            min_t = min(nums[i],min_t)
            max_t = max(nums[i],max_t)
        res = 1
        for d in range(min_cha, max_cha+1):
            f = {}

            for num in nums:
                if num-d in f:
                    f[num] = f[num-d] + 1
                else:
                    f[num] = 1
                res = max(f[num],res)
        return res