The problem is pretty similar to the standard Longest Increasing Subsequence DP problem so it’s easy to guess that this can be solved with DP as well. Define dp[i][j] as longest arithmetic sequence ending at index i having a difference j. Clearly, to find values of dp[i], we iterate from i-1 to 0 (say the iterator is k) and take difference of A[i] with A[k], say diff = A[i]-A[k]. Hence, dp[i][diff] = max(dp[i][diff], dp[k][diff]+1).
The catch here is that how to implement this dp variable? Surely we could make a 2D array but the constraints 0 <= A[i] <= 10000 imply -10000 <= diff <= 10000. Creating a 2D array where each row is of size 20000 is a huge amount of space. And most of these differences won’t even occur in the array so it’s a huge waste as well. Instead, we will implement it as a map of map, as you will see below.
class Solution {
public:
int longestArithSeqLength(vector<int>& A) {
unordered_map<int, unordered_map<int,int>> dp;
int res = 2;
for (int i=0; i<A.size(); i++) {
for (int j=0; j<i; j++) {
int diff = A[i]-A[j];
dp[i][diff] = max(dp[i][diff], dp[j][diff]==0 ? 2 : (dp[j][diff]+1));
res = max(res, dp[i][diff]);
}
}
return res;
}
};
Time complexity: O(nn)
Space complexity: O(nn)