Simulation volume leetcode [general] 1218 Longest definite difference subsequence

1218. The longest definite difference subsequence

Give you an array of integers  arr  And an integer  difference, Please find out and return to arr  The length of the longest isochromatic subsequence in , The difference between adjacent elements in this subsequence is equal to difference .

Subsequence It means that without changing the order of the other elements , Remove from... By deleting some elements or not deleting any elements arr Derived sequence .

Example 1：

Input ：arr = [1,2,3,4], difference = 1
Output ：4
explain ： The longest isochromatic subsequence is [1,2,3,4].
Example  2：

Input ：arr = [1,3,5,7], difference = 1
Output ：1
explain ： The longest arithmetic subsequence is any single element .
Example 3：

Input ：arr = [1,5,7,8,5,3,4,2,1], difference = -2
Output ：4
explain ： The longest isochromatic subsequence is [7,5,3,1].

Tips ：

1 <= arr.length <= 105
-104 <= arr[i], difference <= 104

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        """ Calculate to each number , How many long series are there in total . All from 0 Start calculating """
        pass

    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        res_cnt = {
    }
        for num in arr:
            res_cnt[num] = res_cnt.get(num-difference,0)+1
        return max(res_cnt.values())


def test(data_test):
    s = Solution()
    return s.longestSubsequence(*data_test)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions _ Paper blog -CSDN Blog

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！