Finding Out the Longest Arithmetic Subsequence of Given Differen

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

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

推荐阅读:
掌握这7大SEO优化技巧,提高网站自然排名  网络推广SEO优化是怎么做的?  工信部ICP备案备案系统全新改版,速度更快,用户体验更好  影响网站排名的反向链接细节因素盘点  seo优化六步走网站优化基础策略分享  SEO赚不到钱是病,得治!  影响网站排名的反向链接细节因素盘点  百度上线API主动推送功能  呵护,两个孩子  山水文人作文800字 
评论列表
添加评论