typedeftemplate's blog

Dynamic programming problem help
By typedeftemplate, history, 4 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem can be solved in O (N) by simply calculating the difference of every pair of consecutive elements.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry — I meant to say non-contiguous. I confused two problems. How would I solve the revised problem with dynamic programming?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it +8 Vote: I do not like it

      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++).

      → Reply