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

推荐阅读:
关于节日的作文400字  第一次做蛋炒饭作文100字  赏春作文初中  安全演习心得  属于我一个人的约定  答卷议论文  聪明的乌鸦作文100字  别样的教师节作文  描写大自然的美的作文  齐桓下拜受胙原文及翻译 
评论列表
添加评论