Find Out the Longest Arithmetic Sequence in Array Using Dynamic
- Time:2020-09-12 10:17:13
- Class:Weblog
- Read:30
Given an array A of integers, return the length of the longest arithmetic subsequence in A.
Recall that a subsequence of A is a list A[i_1], A[i_2], …, A[i_k] with 0 <= i_1 < i_2 < … < i_k <= A.length – 1, and that a sequence B is arithmetic if B[i+1] – B[i] are all the same value (for 0 <= i < B.length – 1).
Example 1:
Input: [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.Example 2:
Input: [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].Example 3:
Input: [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].Note:
2 <= A.length <= 2000
0 <= A[i] <= 10000
Find the Longest Arithmetic Sequence by Dynamic Programming Algorithm
Let dp[i][diff] be the maximum length of the Longest Arithmetic Sequence with difference diff and the sequence ends at index i, then we can do a O(N^2) loop to update the maximum length.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: int longestArithSeqLength(vector<int>& A) { if (A.empty()) return 0; int n = A.size(); unordered_map<int, unordered_map<int, int>> dp; int ans = 0; for (int i = 0; i < n; ++ i) { for (int j = 0; j < i; ++ j) { int diff = A[i] - A[j]; dp[i][diff] = max(dp[i][diff], dp[j][diff] + 1); ans = max(ans, dp[i][diff]); } } return ans + 1; } }; |
class Solution { public: int longestArithSeqLength(vector<int>& A) { if (A.empty()) return 0; int n = A.size(); unordered_map<int, unordered_map<int, int>> dp; int ans = 0; for (int i = 0; i < n; ++ i) { for (int j = 0; j < i; ++ j) { int diff = A[i] - A[j]; dp[i][diff] = max(dp[i][diff], dp[j][diff] + 1); ans = max(ans, dp[i][diff]); } } return ans + 1; } };
The longest sequence is the maxmium value occured in dp[i][diff] where i is from 0 to n-1. We use the nested unordered_map (hash map) to store the two dimensional array with O(1) access. The default value is 0 if the key is not existent in the unordered_map.
If the difference is given, and you can find the Longest Arithmetic Sequence using DP as well: Finding Out the Longest Arithmetic Subsequence of Given Difference using Dynamic Programming Algorithm
–EOF (The Ultimate Computing & Technology Blog) —
Recommend: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
Showcase About the Best 30+ Web Tools and Services on the Market
3 Incredible Landing Pages And What We Can Learn From Them
What is Cycle Counting and How to Implement It in Your Retail Bu
4 Reasons Why Your Blog is Struggling to Find an Audience
- Comment list
-
- Comment add