Finding Out the Longest Arithmetic Subsequence of Given Differen

  • 时间:2020-09-18 17:26:09
  • 分类:网络文摘
  • 阅读:93 次

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) —

推荐阅读:
个人站长们常见的很多个网站盈利模式总结  春季饮食宜润肺,常吃炖梨既滋润又养人,口感甜香味道美  这道小学应用题比较难,解题关键是求相遇时间  豆腐搭配鸡蛋做出香酥可口的丸子,营养也很丰富  这道小学奥数题难倒多数学生,解题关键是比例  分享茄子的家常做法,吃起来不油腻,营养美味又下饭  中华人民共和国慈善法(主席令第四十三号)  中华人民共和国深海海底区域资源勘探开发法(主席令第四十二号)  全国人民代表大会常务委员会关于修改《中华人民共和国人口与计划生育法》的决定(主席令第四十一号)  全国人大常委会关于修改《中华人民共和国高等教育法》的决定(主席令第四十号) 
评论列表
添加评论