등차수열

• 처음에는 문제를 잘못 이해해서, 수 몇개를 골라서 순서를 유지한 채로 나열해야 한다고 생각했고, 거기에 맞춰서 O(n^2) DP 풀이를 짰다가 맞왜틀을 심하게 당했다 ㅜ
• 고른 숫자들을 '재배열'해서 등차수열을 만드는 문제라는 것을 뒤늦게 깨닫고 잠시 멘탈이 흔들렸다가, 어떻게든 기존 풀이를 살려보려고 생각해보니, 그냥 처음에 수들을 정렬해놓고서 똑같이 풀면 될거 같았다. 그리고 그렇게 해서 진짜로 ac를 받았다! 나중에 찾아해보니 이분탐색을 이용해서 O(n^2logn)에 푸는 풀이들이 검색되던데, 내방식이 더 빠르네?
• 뽑은 수들의 순서를 유지할때 등차수열의 최대길이를 dp로 푸는 것은, dp[i][j] 를 마지막 두 항이 a_j, a_i 가 되는 등차수열의 최대 길이라고 정의하고 구해주면 된다. 점화식은 dp[i][j] = max_k(dp[j][k]) + 1 (k는 a_j-a_k = a_i-a_j 를 만족) 가 된다. O(n^2)크기의 dp 테이블에 대해, 각 칸을 O(n) 시간에 채워줄수 있다.
• 이것을 좀더 효율적으로 처리하려면, dp 테이블을 dp[i][d]로 바꿔서 등차가 d이고 마지막항이 a_i인 등차수열의 최대 길이로 바꿔써보면 된다. 점화식은 dp[i][a_i-a_j] = dp[j][a_i-a_j] + 1 이 되어서 각 칸을 O(1)에 채울수 있다. a_i가 정해져있을때 가능한 d값의 갯수는 O(n)개이므로 테이블의 크기는 여전히 O(n^2)이기는 한데, d값은 범위가 정해져있지 않으므로 list 대신에 dict를 써서 테이블을 구성하면 된다. 결국 총 시간복잡도는 O(n^2).
• 고른 숫자들을 '재배열'해서 등차수열을 만드는 것은 결국 고른 수들을 '정렬'하는 것이다. 그리고 이것은 미리 정렬된 수열에서 숫자들을 고르는것과 동일하므로, 수열을 미리 정렬하고 정렬된 수열에서 위에 말한 dp를 돌리면 수들을 재배열할수 있을때의 등차수열의 최대 길이를 구할수 있다.

"""Solution code for "BOJ 1994. 등차수열".

- Problem link: https://www.acmicpc.net/problem/1994
- Solution link: http://www.teferi.net/ps/problems/boj/1994

Tags: [dp]
"""

import sys


def main():
    N = int(sys.stdin.readline())
    nums = [int(sys.stdin.readline()) for _ in range(N)]

    if N == 1:
        print('1')
        return

    nums.sort()
    dp = [{} for _ in range(N)]
    for i, num_i, dp_i in zip(range(N), nums, dp):
        for _, num_j, dp_j in zip(range(i), nums, dp):
            diff = num_i - num_j
            dp_i[diff] = dp_j.get(diff, 1) + 1

    print(max(max(dp_i.values()) for dp_i in dp if dp_i))


if __name__ == '__main__':
    main()