题目描述 给定 � n 个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度. 输入格式 第一行是一个整数 � n ,接下来一行包括了 � n 个数。 输出格式 对于每个输入数据,输出你所找出的最长等差数列的长度，N<=4000

算法1

（动态规划）

状态表示：dp[i][j]表示以第i个数结尾，公差为j的等差数列长度。

状态转移方程：对于每个数i，枚举前面的数j，再枚举公差k，若dp[j][k]存在，则可以将i加入这个等差数列中，即dp[i][i-j]=dp[j][k]+1。

最终答案为所有dp[i][j]中的最大值。

时间复杂度

状态总数为O(n^2)，状态转移的时间复杂度为O(n^2)，因此总时间复杂度为O(n^4)。

C++ 代码

算法2

（哈希表）

状态表示：以i,j结尾的最长等差数列长度。

状态转移方程：对于每个数i，枚举前面的数j，算出公差diff，查找哈希表中以j，diff结尾的最长等差数列长度，加上当前数i后的长度，更新以i，diff结尾的最长等差数列长度。

最终答案为所有以i结尾的最长等差数列长度的最大值。

时间复杂度

对于每个数i，枚举前面的数j，因此总时间复杂度为O(n^2)。查找哈希表的时间复杂度为O(1)，因此总时间复杂度为O(n^2)。

C++ 代码