leetcode-Algorithms-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]。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-arithmetic-subsequence-of-given-difference
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

动态规划，以Map存储，寻找之前的key，然后根据value判断。

代码

public class Solution_1218 {
    public static void main(String[] args) {
    int[] arr = {
    1, 5, 7, 8, 5, 3, 4, 2, 1};int difference = -2;longestSubsequence(arr, difference);longestSubsequence_dp(arr, difference);}public static int longestSubsequence(int[] arr, int difference) {
    Deque<Integer> stack = new ArrayDeque<>();for (int i : arr) {
    stack.addLast(i);}int maxLength = 0;for (int i = 0; i < arr.length; i++) {
    int target = stack.removeFirst();Deque<Integer> copy = new ArrayDeque<>(stack);int y = 1;for (int a : copy) {
    if (target == a - difference * y) {
    y++;}}maxLength = Math.max(maxLength, y);}return maxLength;}public static int longestSubsequence_dp(int[] arr, int difference) {
    HashMap<Integer, Integer> hashMap = new HashMap<>();int maxLength = 0;for (int i = 0; i < arr.length; i++) {
    if (hashMap.containsKey(arr[i] - difference)) {
    int value1 = hashMap.get(arr[i] - difference);int value2 = hashMap.getOrDefault(arr[i], 0);int value3 = Math.max(value1 + 1, value2);hashMap.put(arr[i], value3);} else {
    if (!hashMap.containsKey(arr[i])) {
    hashMap.put(arr[i], hashMap.getOrDefault(arr[i], 0) + 1);}}}for (int i : hashMap.keySet()) {
    maxLength = Math.max(maxLength, hashMap.get(i));}return maxLength;}
}