Hi everyone,
I am pretty new to dynamic programming, and I have been struggling with the following problem:
Given an array of integers, how can I find the longest contiguous arithmetic subsequence? For instance, if our entries are 10, 3, 5, 7, 9, 11, 5, 8, 7, 13, 14, then I would have to return "5" since 3, 5, 7, 9, 11 forms the longest contiguous arithmetic subsequence.
I thought about defining dp[i][j] to be the longest contiguous arithmetic subsequence ending at index i with common difference equal to j, but I can't really come up with the transitions properly.
I would really appreciate it if someone could please help me with this problem.
If you're looking for an N^2 solution, you don't need DP. You can simply iterate for left pointer in contiguous sequence and continue increasing the right pointer while possible.
The problem can be solved in O (N) by simply calculating the difference of every pair of consecutive elements.
Sorry — I meant to say non-contiguous. I confused two problems. How would I solve the revised problem with dynamic programming?
Suppose that you maintain a map $$$M$$$ for every element $$$i$$$ in which $$$M_i[delta]$$$ = Size of the biggest arithmetic sequence that ends on position $$$i$$$ and has ratio equal to $$$delta$$$. To calculate this for each $$$i$$$, you can iterate through all previous positions $$$j$$$ and do $$$M_i[V_i - V_j] = max (M_i[V_i - V_j], M_j[V_i - V_j] + 1)$$$.
This leads to an $$$O (N^2 log N)$$$ solution if you use maps, or $$$O (N^2)$$$ if using hash maps (unordered_map in C++).