Longest Arithmetic subsequence of given difference

XXX. Longest Arithmetic Subsequence of Given Difference

Dynamic Programming

Hash Map

Problem Statement:

Given an integer array arr and an integer difference, find the length of the longest subsequence in the array such that the difference between consecutive elements is equal to difference.

Return the length of the longest such subsequence.

Algorithm:

1. Use a HashMap for Dynamic Programming:

   The key in the map represents the value of an element, and the value represents the length of the longest subsequence ending with that element.

2. Iterate Through the Array:

   For each element in the array, check if there exists a previous element with the required difference (a - difference). Update the current element's value in the map as previous length + 1.

3. Update the Answer:

   Track the maximum length of any subsequence found during the iteration.

Complexity:

Time Complexity: O(n), where n is the length of the array, as we traverse the array once and perform constant-time operations for each element.
Space Complexity: O(n), due to the space used by the hash map.

Java Implementation:

class Solution {
    public int longestSubsequence(int[] arr, int difference) {
        Map dp = new HashMap<>();
        int answer = 1; // Initialize the answer with 1 since a single element is a valid subsequence

        // Iterate over each element in the array
        for (int a : arr) {
            // Check if there exists a previous element with the required difference
            int beforeA = dp.getOrDefault(a - difference, 0);

            // Update the current element's value in the map
            dp.put(a, beforeA + 1);

            // Update the maximum length found so far
            answer = Math.max(answer, dp.get(a));
        }

        return answer; // Return the length of the longest subsequence
    }
}