https://leetcode.com/problems/longest-arithmetic-sequence/
X. https://leetcode.com/problems/longest-arithmetic-sequence/discuss/274701/Java-DP-O(n2)-solution-with-explanation
https://leetcode.com/problems/longest-arithmetic-sequence/discuss/274611/JavaC%2B%2BPython-DP
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 <= 20000 <= A[i] <= 10000
The main idea is to maintain a map of differences seen at each index.
We iteratively build the map for a new index
For each pair of indices
i, by considering all elements to the left one-by-one.For each pair of indices
(i,j) and difference d = A[i]-A[j] considered, we check if there was an existing chain at the index j with difference d already.- If yes, we can then extend the existing chain length by 1.
- Else, if not, then we can start a new chain of length
2with this new differencedand(A[j], A[i])as its elements.
At the end, we can then return the maximum chain length that we have seen so far.
Time Complexity: O(n^2)
Space Complexity: O(n^2)
class Solution {
public int longestArithSeqLength(int[] A) {
if (A.length <= 1) return A.length;
int longest = 0;
// Declare a dp array that is an array of hashmaps.
// The map for each index maintains an element of the form-
// (difference, length of max chain ending at that index with that difference).
HashMap<Integer, Integer>[] dp = new HashMap[A.length];
for (int i = 0; i < A.length; ++i) {
// Initialize the map.
dp[i] = new HashMap<Integer, Integer>();
}
for (int i = 1; i < A.length; ++i) {
int x = A[i];
// Iterate over values to the left of i.
for (int j = 0; j < i; ++j) {
int y = A[j];
int d = x - y;
// We at least have a minimum chain length of 2 now,
// given that (A[j], A[i]) with the difference d,
// by default forms a chain of length 2.
int len = 2;
if (dp[j].containsKey(d)) {
// At index j, if we had already seen a difference d,
// then potentially, we can add A[i] to the same chain
// and extend it by length 1.
len = dp[j].get(d) + 1;
}
// Obtain the maximum chain length already seen so far at index i
// for the given differene d;
int curr = dp[i].getOrDefault(d, 0);
// Update the max chain length for difference d at index i.
dp[i].put(d, Math.max(curr, len));
// Update the global max.
longest = Math.max(longest, dp[i].get(d));
}
}
return longest;
}https://leetcode.com/problems/longest-arithmetic-sequence/discuss/274611/JavaC%2B%2BPython-DP
dp[diff][index] + 1 equals to the length of arithmetic sequence at index with difference diff. public int longestArithSeqLength(int[] A) {
Map<Integer, Map<Integer, Integer>> dp = new HashMap<>(); // <difference, <Index of Element for this difference, count of sequence>>
int max = 2;
for (int i = 0; i < A.length; i++) {
for (int j = i + 1; j < A.length; j++) {
int a = A[i], b = A[j];
Map<Integer, Integer> diffMap = dp.computeIfAbsent(b - a, c -> new HashMap<>());
int currMax = Math.max(diffMap.getOrDefault(j, 0), diffMap.getOrDefault(i, 0) + 1); // if the element for the difference is i (variable a = A[i]), then we can add 1 to the count of sequence
diffMap.put(j, currMax);
max = Math.max(max, currMax + 1);
}
}
return max;
}
Each cell is a hashmap with
difference as key and length as value| 20 | 1 | 15 | 3 | 10 | 5 | |
|---|---|---|---|---|---|---|
| 20 | 20:1 | -19:2 | -5:2 | -17:2 | -10:2 | -15:2 |
| 1 | 14:2 | 2:2 | 9:2 | 4:2 | ||
| 15 | -12:2 | -5:3 | -10:2 | |||
| 3 | 7:2 | 2:3 | ||||
| 10 | -5:4 | |||||
| 5 |
public int longestArithSeqLength(int[] A) {
Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
int res = 1;
int n = A.length;
Map<Integer, Integer> s = new HashMap<>();
s.put(A[0], 1);
map.put(0, s);
for (int i = 1; i < n; i++) {
Map<Integer, Integer> cur = new HashMap<>();
for (int j = 0; j < i; j++) {
int diff = A[i] - A[j];
cur.put(diff, 2);
Map<Integer, Integer> pre = map.get(j);
if (pre.containsKey(diff)) {
cur.put(diff, pre.get(diff) + 1);
}
res = Math.max(cur.get(diff), res);
}
map.put(i, cur);
}
return res;
}