1218. Longest Arithmetic Subsequence of Given Difference

leetcode medium

#array#csharp#dynamic-programming#hash-table#leetcode#math#medium

Task

Дан массив целых чисел arr и целое число difference. Верните длину самой длинной подпоследовательности в arr, которая является арифметической последовательностью, так что разница между соседними элементами в подпоследовательности равна difference.

Подпоследовательность — это последовательность, которую можно получить из arr, удалив некоторые или ни одного элемента, не меняя порядок оставшихся элементов.

Пример:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2

Output: 4

Explanation: The longest arithmetic subsequence is [7,5,3,1].

C# solution

matched/original

public class Solution {
    public int LongestSubsequence(int[] arr, int difference) {
        Dictionary<int, int> dp = new Dictionary<int, int>();
        int answer = 1;
        
        foreach (int a in arr) {
            int beforeA = dp.ContainsKey(a - difference) ? dp[a - difference] : 0;
            dp[a] = beforeA + 1;
            answer = Math.Max(answer, dp[a]);
        }
        
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LongestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> dp = new unordered_map<int, int>();
        int answer = 1;
        
        foreach (int a in arr) {
            int beforeA = dp.count(a - difference) ? dp[a - difference] : 0;
            dp[a] = beforeA + 1;
            answer = max(answer, dp[a]);
        }
        
        return answer;
    }
}

Java solution

matched/original

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

JavaScript solution

matched/original

var longestSubsequence = function(arr, difference) {
    let dp = new Map();
    let answer = 1;
    
    for (let a of arr) {
        let beforeA = dp.get(a - difference) || 0;
        dp.set(a, beforeA + 1);
        answer = Math.max(answer, dp.get(a));
    }
    
    return answer;
};

Python solution

matched/original

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        answer = 1
        
        for a in arr:
            before_a = dp.get(a - difference, 0)
            dp[a] = before_a + 1
            answer = max(answer, dp[a])
        
        return answer

Go solution

matched/original

func longestSubsequence(arr []int, difference int) int {
    dp := make(map[int]int)
    answer := 1
    
    for _, a := range arr {
        beforeA := dp[a - difference]
        dp[a] = beforeA + 1
        if dp[a] > answer {
            answer = dp[a]
        }
    }
    
    return answer
}

Explanation

Algorithm

Инициализируйте пустой хеш-таблицу dp и установите answer = 1.

Итеративно обработайте массив arr. Для каждого элемента arr[i]:

Вычислите before_a, максимальную длину арифметической подпоследовательности, заканчивающейся на arr[i] - difference:

- если arr[i] - difference существует в dp, установите before_a = dp[arr[i] - difference].

- в противном случае, установите before_a = 0.

Установите dp[arr[i]] = before_a + 1, обновите answer как answer = max(answer, dp[arr[i]]).

Верните answer после завершения итерации.

😎