Find Out the Longest Arithmetic Sequence in Array Using Dynamic

  • 时间:2020-09-12 10:17:13
  • 分类:网络文摘
  • 阅读:93 次

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

推荐阅读:
How to Flip Equivalent Binary Trees?  How to Implement Quicksort Algorithm in Python – the Pytho  How to Compute the Clumsy Factorials using Iterative Algorithm?  How to Convert Float Number (Fraction) to Hexadecimal in Python?  4 Tips You Shouldn’t Miss While Creating Your Ideal Websit  SQL Algorithm to Compute Shortest Distance in a Plane  How to Count Univalue Subtrees in a Binary Tree?  Have Writer’s Block? Try These Content Ideation Tools for Market  Quick Ways to Relax Once You’ve Hit Publish  How to Prepare Your SEO Strategy for the Internet of Things 
评论列表
添加评论