Question

1218. 最长定差子序列

English Version

题目描述

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

 

示例 1：

输入：arr = [1,2,3,4], difference = 1
输出：4
解释：最长的等差子序列是 [1,2,3,4]。

示例 2：

输入：arr = [1,3,5,7], difference = 1
输出：1
解释：最长的等差子序列是任意单个元素。

示例 3：

输入：arr = [1,5,7,8,5,3,4,2,1], difference = -2
输出：4
解释：最长的等差子序列是 [7,5,3,1]。

 

提示：

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

解法

方法一：动态规划

时间复杂度 $O(n)$。

class Solution:
  def longestSubsequence(self, arr: List[int], difference: int) -> int:
    f = defaultdict(int)
    for x in arr:
      f[x] = f[x - difference] + 1
    return max(f.values())

class Solution {
  public int longestSubsequence(int[] arr, int difference) {
    Map<Integer, Integer> f = new HashMap<>();
    int ans = 0;
    for (int x : arr) {
      f.put(x, f.getOrDefault(x - difference, 0) + 1);
      ans = Math.max(ans, f.get(x));
    }
    return ans;
  }
}

class Solution {
public:
  int longestSubsequence(vector<int>& arr, int difference) {
    unordered_map<int, int> f;
    int ans = 0;
    for (int x : arr) {
      f[x] = f[x - difference] + 1;
      ans = max(ans, f[x]);
    }
    return ans;
  }
};

func longestSubsequence(arr []int, difference int) (ans int) {
  f := map[int]int{}
  for _, x := range arr {
    f[x] = f[x-difference] + 1
    ans = max(ans, f[x])
  }
  return
}

function longestSubsequence(arr: number[], difference: number): number {
  const f: Map<number, number> = new Map();
  for (const x of arr) {
    f.set(x, (f.get(x - difference) ?? 0) + 1);
  }
  return Math.max(...f.values());
}

/**
 * @param {number[]} arr
 * @param {number} difference
 * @return {number}
 */
var longestSubsequence = function (arr, difference) {
  const f = new Map();
  for (const x of arr) {
    f.set(x, (f.get(x - difference) || 0) + 1);
  }
  return Math.max(...f.values());
};