Finding Out the Longest Arithmetic Subsequence of Given Difference using Dynamic Programming Algorithm

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.

Example 1:
Input: arr = [1,2,3,4], difference = 1
Output: 4
Explanation: The longest arithmetic subsequence is [1,2,3,4].

Example 2:
Input: arr = [1,3,5,7], difference = 1
Output: 1
Explanation: The longest arithmetic subsequence is any single element.

Example 3:
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].

Constraints:
1 <= arr.length <= 10^5
-10^4 <= arr[i], difference <= 10^4

Hints:
Use dynamic programming.
Let dp[i] be the maximum length of a subsequence of the given difference whose last element is i.
dp[i] = 1 + dp[i-k]

Dynamic Programming Algorithm to Find Out the Longest Arithmetic Subsequence

Let the maximum length of the subsequence be dp[i] whose last element is i, we can easily deduce that dp[i + k] = 1 + dp[i] or dp[i] = 1 + dp[i-k]. Iterating the array, and record the intermediate answers in a hash map – this requires O(N) time and O(N) space.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        if (arr.empty()) return 0;
        unordered_map<int, int> dp;
        int ans = 0;
        for (const auto n: arr) {
            dp[n] = 1 + dp[n - difference];
            ans = max(ans, dp[n]);
        }
        return ans;
    }
};

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        if (arr.empty()) return 0;
        unordered_map<int, int> dp;
        int ans = 0;
        for (const auto n: arr) {
            dp[n] = 1 + dp[n - difference];
            ans = max(ans, dp[n]);
        }
        return ans;
    }
};

If a key is not found in the unordered_map, the default value will be zero for a integer. You could, use the following to explicitly set the values in the hash map.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        if (arr.empty()) return 0;
        unordered_map<int, int> dp;
        int ans = 0;
        for (const auto n: arr) {
            if (dp.find(n - difference) != dp.end()) {
                dp[n] = 1 + dp[n - difference];
            } else {
                dp[n] = 1;
            }
            ans = max(ans, dp[n]);
        }
        return ans;
    }
};

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        if (arr.empty()) return 0;
        unordered_map<int, int> dp;
        int ans = 0;
        for (const auto n: arr) {
            if (dp.find(n - difference) != dp.end()) {
                dp[n] = 1 + dp[n - difference];
            } else {
                dp[n] = 1;
            }
            ans = max(ans, dp[n]);
        }
        return ans;
    }
};

The bruteforce algorithm may also work, but takes longer computational time: start with each number, jump to next available sequence, find each longest Arithmetic Subsequence.

The Dynamic Programming Algorithm is efficient as it remembers previous intermediate solutions using a O(N) hash map.

If the difference value is not given, and you are asked to find out the longest Arithmetic Subsequence (Find Out the Longest Arithmetic Sequence in Array Using Dynamic Programming Algorithm), you can still use the Dynamic Programming Algorithm, however, the computational complexiy will need to be O(N^2).

–EOF (The Ultimate Computing & Technology Blog) —