1218-最长定差子序列

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

给你一个整数数组 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

方法一：动态规划

下文为方便叙述将 difference 简写成 d。

我们从左往右遍历 arr，并计算出以 arr}[i] 为结尾的最长的等差子序列的长度，取所有长度的最大值，即为答案。

令 dp}[i] 表示以 arr}[i] 为结尾的最长的等差子序列的长度，我们可以在 arr}[i] 左侧找到满足 arr}[j]=\textit{arr}[i]-d 的元素，将 arr}[i] 加到以 arr}[j] 为结尾的最长的等差子序列的末尾，这样可以递推地从 dp[j] 计算出 dp[i]。由于我们是从左往右遍历 arr 的，对于两个相同的元素，下标较大的元素对应的 dp 值不会小于下标较小的元素对应的 dp 值，因此下标 j 可以取满足 j<i 且 arr}[j]=\textit{arr}[i]-d 的所有下标的最大值。故有转移方程

\textit{dp}[i] = \textit{dp}[j] + 1

由于我们总是在左侧找一个最近的等于 arr}[i]-d 元素并取其对应 dp 值，因此我们直接用 dp}[v] 表示以 v 为结尾的最长的等差子序列的长度，这样 dp}[v-d] 就是我们要找的左侧元素对应的最长的等差子序列的长度，因此转移方程可以改为

\textit{dp}[v] = \textit{dp}[v-d] + 1

最后答案为 \max{\textit{dp}\。

[sol1-Python3]
1
2
3
4
5
6
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())
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int longestSubsequence(vector<int> &arr, int difference) {
        int ans = 0;
        unordered_map<int, int> dp;
        for (int v: arr) {
            dp[v] = dp[v - difference] + 1;
            ans = max(ans, dp[v]);
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
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;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int LongestSubsequence(int[] arr, int difference) {
        int ans = 0;
        Dictionary<int, int> dp = new Dictionary<int, int>();
        foreach (int v in arr) {
            int prev = dp.ContainsKey(v - difference) ? dp[v - difference] : 0;
            if (dp.ContainsKey(v)) {
                dp[v] = prev + 1;
            } else {
                dp.Add(v, prev + 1);
            }
            ans = Math.Max(ans, dp[v]);
        }
        return ans;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
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
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
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;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 arr 的长度。

  • 空间复杂度：O(n)。哈希表需要 O(n) 的空间。

 Comments
On this page
1218-最长定差子序列