# Given an array A of integers, return the length of the longest arithmetic subsequence in A.
#
# Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with 0 <= i_1 < i_2 < ... < i_k <= A.length -
# 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).
#
#
#
# Example 1:
#
# Input: [3,6,9,12]
# Output: 4
# Explanation:
# The whole array is an arithmetic sequence with steps of length = 3.
# Example 2:
#
# Input: [9,4,7,2,10]
# Output: 3
# Explanation:
# The longest arithmetic subsequence is [4,7,10].
# Example 3:
#
# Input: [20,1,15,3,10,5,8]
# Output: 4
# Explanation:
# The longest arithmetic subsequence is [20,15,10,5].
#
#
# Note:
#
# 2 <= A.length <= 2000
# 0 <= A[i] <= 10000
import collections


class Solution(object):
    def longestArithSeqLength(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        n = len(A)
        dp, res = [collections.defaultdict(int) for i in xrange(n)], 0

        for i in xrange(1, n):
            for j in reversed(xrange(i)):
                diff = A[i] - A[j]
                dp[i][diff] = max(1, dp[i][diff])
                if diff in dp[j]:
                    dp[i][diff] = max(dp[i][diff], 1 + dp[j][diff])
                res = max(res, dp[i][diff] + 1)

        return res


if __name__ == '__main__':
    print Solution().longestArithSeqLength([6, 5, 4, 3, 10, 9, 8, 7, 6, 6, 6, 5, 4, 3, 2, 1])
    print Solution().longestArithSeqLength(
        [22, 8, 57, 41, 36, 46, 42, 28, 42, 14, 9, 43, 27, 51, 0, 0, 38, 50, 31, 60, 29, 31, 20, 23, 37, 53, 27, 1, 47,
         42, 28, 31, 10, 35, 39, 12, 15, 6, 35, 31, 45, 21, 30, 19, 5, 5, 4, 18, 38, 51, 10, 7, 20, 38, 28, 53, 15, 55,
         60, 56, 43, 48, 34, 53, 54, 55, 14, 9, 56, 52])
    print Solution().longestArithSeqLength([20, 1, 15, 3, 10, 5, 8])
    print Solution().longestArithSeqLength([24, 13, 1, 100, 0, 94, 3, 0, 3])
    print Solution().longestArithSeqLength([0, 8, 45, 88, 48, 68, 28, 55, 17, 24])
