Longest Arithmetic Subsequence — Solution & Editorial

Back to the Problem

dp[i][d] = longest AP ending at i with common difference d; for each pair (j, i) extend dp[j][a_i−a_j]. Store the per-index difference map.

Complexity: O(N²)