当前位置：首页 > article >正文

leetcode 1027 最长等差数列题目的思考

article 2025/1/22 6:49:25

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

查看全文

http://www.kler.cn/a/350288.html