CodeForces 256A （dp）

CodeForces 256A （dp）

A. Almost Arithmetical Progression time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

Gena loves sequences of numbers. Recently, he has discovered a new type of sequences which he called an almost arithmetical progression. A sequence is an almost arithmetical progression, if its elements can be represented as:

• a1?=?p, where p is some integer;
• ai?=?ai?-?1?+?(?-?1)i?+?1·q (i?>?1), where q is some integer.

  Right now Gena has a piece of paper with sequence b, consisting of n integers. Help Gena, find there the longest subsequence of integers that is an almost arithmetical progression.

  Sequence s1,??s2,??...,??sk is a subsequence of sequence b1,??b2,??...,??bn, if there is such increasing sequence of indexesi1,?i2,?...,?ik (1??≤??i1??i2??ik??≤??n), that bij??=??sj. In other words, sequence s can be obtained from b by crossing out some elements.

  Input

  The first line contains integer n (1?≤?n?≤?4000). The next line contains n integers b1,?b2,?...,?bn (1?≤?bi?≤?106).

  Output

  Print a single integer — the length of the required longest subsequence.

  Sample test(s) input

  2
  3 5
  

  output

  2
  

  input

  4
  10 20 10 30
  

  output

  3
  

  Note

  In the first test the sequence actually is the suitable subsequence.

  In the second test the following subsequence fits: 10,?20,?10.

  
  

  題意：從給定的有序的序列中找最多的p，q，p，q.

  
  

  
  

  dp[i][j]:代表在第 i 個數前一個數是 j 的情況下的最多值，

  則：

  dp[i][j]=dp[j][pre] + 1,

  
  

  #include
  #include
  #include
  #include
  #include