---
tags: VNOJ, DP, Time Optimized, Fibonacci, SPyofgame
---

Dãy số dài nhất
===

[https://oj.vnoi.info/problem/skfib](https://oj.vnoi.info/problem/skfib)

-----

###### Co-Author: [kazamahoang](http://www.codeforces.com/profile/phaicogiaiquocgia)

###### Tags: DP, Time Optimized, Fibonacci

-----
### Hướng dẫn

Nhận thấy $N \leq 2500$ và số truy vấn $Q \leq 15$ tạo điều kiện cho thuật quy hoạch động $O(n^2)$

Ý tưởng đơn giản là định nghĩa $f[i][j][p]$ là xét đến $[i]$, số cuối trong dãy là $[j]$, số trước đó trong dãy là $[p]$, tất nhiên $i > j > p$. Và chỉ thêm $[i]$ vào dãy khi $a[i] - a[j] = a[p]$ và gán $f[i][j][p] = max(f[j][p][q] + [a_i - a_j = a_p])$ với $[x = y]$ trả về $1$ khi đúng và $0$ khi sai.

Vì khi cố định $[i][j]$ ta biết được $[p]$. Ta giảm chiều bằng cách định nghĩa $f[i][j]$ là xét đến $[i]$, số cuối trong dãy là $[j]$. Và duyệt qua các vị trí $[p]$ có $a[i] - a[j] = a[p]$ để thêm vào dãy. Lúc này ta có $f[i][j] = max(f[j][p] + 1\ |\ a_i - a_j = a_p)$

Nhận thấy ta chỉ quan tâm độ dài. Và nó tăng dần qua mỗi $i$. Nên khi cố định $[i][j]$ thì vị trí có $p$ gần nhất sẽ dài hơn. Vậy ta gọi mảng $p[x]$ là vị trí số $p$ cuối cùng có tồn tại cặp $(i, j)$ mà $a_p = x = a_i - a_j$. Lúc này ta chỉ cần cập nhật $f[i][j] = max(f[j][p[a_i - a_j]] + 1\ ,\ 2)$ số $2$ đến từ việc dãy $2$ phần tử ${a_i, a_j}$ cũng hợp lệ theo đề bài.

:::warning
### Lưu ý:
- Vì bài này có cả số âm nên bạn phải dịch giá trị lên nếu như ngôn ngữ không hỗ trợ số âm.
- Vì bài này time limit chặt nên bạn phải cài khéo. Tức là tối ưu hằng số thời gian đủ nhỏ để qua.
:::

-----
### Code

> For $V = max(|a_i|)$
> **Constant:** $c_0 = \frac{1}{4}$
> **Time:** $O(q \times n^2 + V)$ total - $O(n^2 + n)$ query
> **Space:** $O(n^2 + V)$ total
> **Algo:** DP, Time Optimized

#include <iostream>

using namespace std;

const int LIM_N = 2501;
const int LIM_A = 2e6;

int n;
int a[LIM_N];
int f[LIM_N][LIM_N];
int p[2 * LIM_A + 1] = {};

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);
    
    int q;
    cin >> q;

    while (q-->0)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
            cin >> a[i];

        int res = 2;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = i + 1; j <= n; ++j)
            {
                f[i][j] = max(2, f[p[a[j] - a[i] + LIM_A]][i] + 1);
                if (res < f[i][j])
                    res = f[i][j];
            }
            p[a[i] + LIM_A] = i;
        }
        
        for (int i = 1; i <= n; ++i) p[a[i] + LIM_A] = 0;
        cout << res << "\n";
    }
    

    return 0;
}