题目描述

Description

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:

$a_1 = p$, where p is some integer;
ai = $a_{i-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 indexes i1, i2, …, ik (1 ≤ i1 < i2 < … < ik ≤ n), that $b_{i_j} = s_j$. 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 ≤ 10^6).

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

题目链接

http://codeforces.com/problemset/problem/255/C

解题思路

题目大意：给出一个序列b，求b中形如p，p - q，p，p - q，p，p - q，…这样出现的最长子序列的最大长度。

这题第一反应是O(n^3)算法，没有试验到底会不会TLE。再纠结了1小时之后决定写一个DP试试。

所以我们设dp[i][j]，表示倒数第一个数是a[i]，倒数第二个数是a[j]的子序列的最大长度。然后观察我们要找的子序列的规律，有动态转移方程：dp[i][j] = dp[j][k] + 1，此处的k是使a[i] == a[j]的j的值。也就是说，dp[i][j]的值是在遇到a[i]这个元素之前的子序列长度加1得到的。首先应该先设任意两个数的dp[i][j] = 2才可以。

AC代码

62800 KB/109 ms/GNU G++ 4.9.2

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int dp[4005][4005], a[4005];
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < n; i++)
        {
            scanf("%d", a + i);
        }
        int ans = 1;
        for (int i = 0; i < n; i++)
        {
            int k = -1;
            for (int j = 0; j < i; j++)
            {
                if (k == -1) dp[i][j] = 2;
                else dp[i][j] = dp[j][k] + 1;
                if (a[j] == a[i]) k = j;
                ans = max(ans, dp[i][j]);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}