class Solution {
public:
int longestSubsequence(vector<int>& arr, int difference) {
}
};
1218. 最长定差子序列
给你一个整数数组 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原站题解
javascript 解法, 执行用时: 120 ms, 内存消耗: 51.7 MB, 提交时间: 2023-02-10 10:27:43
/**
* @param {number[]} arr
* @param {number} difference
* @return {number}
*/
var longestSubsequence = function(arr, difference) {
let ans = 0;
const dp = new Map();
for (const v of arr) {
dp.set(v, (dp.get(v - difference) || 0) + 1);
ans = Math.max(ans, dp.get(v));
}
return ans;
};
java 解法, 执行用时: 44 ms, 内存消耗: 56.1 MB, 提交时间: 2023-02-10 10:27:29
class Solution {
public int longestSubsequence(int[] arr, int difference) {
int ans = 0;
Map<Integer, Integer> dp = new HashMap<Integer, Integer>();
for (int v : arr) {
dp.put(v, dp.getOrDefault(v - difference, 0) + 1);
ans = Math.max(ans, dp.get(v));
}
return ans;
}
}
golang 解法, 执行用时: 88 ms, 内存消耗: 8.1 MB, 提交时间: 2023-02-10 10:27:12
func longestSubsequence(arr []int, difference int) (ans int) {
dp := map[int]int{}
for _, v := range arr {
dp[v] = dp[v-difference] + 1
if dp[v] > ans {
ans = dp[v]
}
}
return
}
python3 解法, 执行用时: 96 ms, 内存消耗: 25.1 MB, 提交时间: 2023-02-10 10:26:57
# 动态规划，dp[v]表示以v结尾的最长等差子序列
class Solution:
def longestSubsequence(self, arr: List[int], difference: int) -> int:
dp = defaultdict(int)
for v in arr:
dp[v] = dp[v - difference] + 1
return max(dp.values())