Finding Out the Longest Arithmetic Subsequence of Given Differen
- 时间:2020-09-18 17:26:09
- 分类:网络文摘
- 阅读:87 次
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^4Hints:
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) —
推荐阅读:How to Compute the Catalan Numbers using Dynamic Programming Alg C++ Coding Reference: Partial Sorting with nth_element from Algo Microbit Programming: Introduction to AI – Letting Compute Subtract the Product and Sum of Digits of an Integer Leetcode’s Online Code Debugger Algorithm to Remove a Interval from Segments How to Start a Podcast for a Blog How to Change Your Blogging Focus Without Missing a Beat A 7-Step Guide to Creating Your Content Editorial Calendar for 2 How to Find and Hire a Ghostwriter for Your Blog
- 评论列表
-
- 添加评论