Dãy số dài nhất

View as PDF
Submit solution
Points: 0.91 (partial)
Time limit: 0.9s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
IOICAMP
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy ~A~ gồm ~N~ số nguyên. Một dãy con của dãy ~A~ là dãy gồm các phần tử ~A_{i_1}~, ~A_{i_2}~, ..., ~A_{i_M}~ thỏa mãn: ~1 \le i_1 < i_2 < \dots < i_M \le N~. Hãy tìm dãy con ~B~ dài nhất thỏa mãn điều kiện: ~B_i = B_{i - 1} + B_{i - 2}~ với ~i \ge 3~.

Input

  • Dòng ~1~: ~T~ - số test ~(1 \le T \le 15)~.

  • Tiếp theo là ~2T~ dòng mô tả các test, mỗi test gồm:

    • Dòng ~1~: ~N~ ~(3 \le N \le 2500)~.
    • Dòng ~2~: ~N~ số ~A_1~, ~A_2~, ..., ~A_N~. Các số có giá trị tuyệt đối không quá ~10^{6}~.

Output

Gồm ~T~ dòng, mỗi dòng ghi ~1~ số nguyên là độ dài dãy con dài nhất.

Sample Input

1
7
-20 87 20 0 20 100 22

Sample Output

4

Comments

Please read the guidelines before commenting.