CF 156 div 1

A: Given a sequence of 4000 integers, find the longest sequence with p, p - q,  p, p-q, p, p-q, ...
1 <= a[i] <= 10^6

You need O(n^2) algorithm. If you check all pairs of (i,j) then extend to the rest of the sequence, it is O(n^3). However, if you try to do dp without checking the whole sequence for each (i,j) pair, you need to put a[i] into your state, however the max a[i] can be 10^6 and an array with a[4000][10^6] is too big. The rescue is that you don't have to use the raw a[i] value, you only have 4000 distinct values and you can map them into 1, 2, ..., 4000. That's it.

To map values, an easy way is to use stl map
or you can make a copy of a[] to b[], then sort and unique b[],
then a[i] would be the index of a[i] in b[] using binary search, or stl lower_bound.

The actual dp needs two arrays, next[i][k] and dp[i][k]
next[i][k] is the next pos in i+1..n-1 with value = k
dp[i][k] is the length of best subseq ending at pos=i and prev element is equal to k.

for i=0 to n-1
for k=0 to n-1 // values mapped to 0 .. n-1 since at most n distinct elements
  dp[i][k] = 1

for i=0 to n-1
for j=i+1 to n-1
  if next[i][a[j]] not init, then next[i][a[j]] = j

for i=0 to n-1
for k=0 to n-1
  j = next[i][k]  // look for next stop
  if j is a valid index, then update dp[j][a[i]] with dp[i][k] + 1 if this is a longer subseq

// another dp is to use dp[i][k] as length of best subseq starting at i and with next value = k
for i = n-1 to 0
for j = i+1 to n-1
  dp[i][a[j]] = 2
  nxt = next[j][a[i]]
  if nxt is a valid index
    dp[i][a[j]] = dp[j][nxt] + 1

// this avoids taking max and likely faster