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

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

int main()
{
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];

int res = 0;
unordered_map<int, int> dp[n];
for (int i = 1; i < n; i++)
{
for (int j = 0; j < i; j++)
{
int diff = a[i] - a[j];
if (dp[j].count(diff))
dp[i][diff] = dp[j][diff] + 1;
else
dp[i][diff] = 2;
res = max(res, dp[i][diff]);
}
}
cout << res << endl;
return 0;
}

相关问题

题目描述 给定 � 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++ 代码

题目描述 给定一组数和一个给定的数 n , 求出在这一组数中,比 n 大的所

给定一组数和一个给定的数 n ,我们可以通过遍历这一组数，将比 n 大的数字记录下来。首先，我们设定一个空列表，用来存放比 n 大的数字。然后，我们依次遍历这一组数，如果当前的数字大于 n ，就将它加入到列表中。最后，我们得到的列表就是那些比 n 大的数。

举例来说，假设给定的一组数是 [1, 3, 5, 7, 9] ，给定的数是 4 。我们通过遍历这一组数，发现有两个数字比 4 大，它们分别是 5 和 7 ，所以最终得到的列表就是 [5, 7] 。

在实际的编程中，我们也可以通过一个循环，遍历这一组数，然后利用条件语句来判断是否比 n 大，如果是就将它加入到列表中。另外，也可以使用一些内置的函数来简化这个过程，例如使用列表解析或者 filter 函数。

总之，通过遍历给定的一组数，并利用条件判断或者内置函数，我们可以很容易地找出比给定数 n 大的所有数字。