C++ 等差数列最长长度 - 6237 题解

"C++ 等差数列最长长度 - 6237 题解"\n\n本文提供 C++ 代码实现，解决 LeetCode 6237 等差数列问题，找出给定数组中最长的等差数列长度。\n\n\n题目描述\n\n给定 "n" 个数,从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.\n\n输入格式\n\n第一行是一个整数 "n" ,接下来一行包括了 "n" 个数。\n\n输出格式\n\n对于每个输入数据,输出你所找出的最长等差数列的长度\n\n输入输出样例内容：\n\n输入样例：\n\n5\n1 2 3 5 7\n\n输出样例：\n\n3\n\n解题思路：\n\n1. 首先对输入的数列进行排序。\n2. 定义一个二维数组dp，dp[i][j]表示以第i个数结尾，差为j的等差数列的最长长度。\n3. 对于每个数dp[i][j]，遍历前面的所有数，找到差为j的等差数列的最长长度。\n4. 最终答案为dp[i][j]中的最大值。\n\n代码实现：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nint main() {\n int n;\n cin >> n;\n vector<int> nums(n);\n for (int i = 0; i < n; i++) {\n cin >> nums[i];\n }\n \n sort(nums.begin(), nums.end());\n \n vector<vector<int>> dp(n, vector<int>(20001, 1));\n int ans = 1;\n for (int i = 1; i < n; i++) {\n for (int j = 0; j < i; j++) {\n int diff = nums[i] - nums[j];\n dp[i][diff + 10000] = max(dp[i][diff + 10000], dp[j][diff + 10000] + 1);\n ans = max(ans, dp[i][diff + 10000]);\n }\n }\n \n cout << ans << endl;\n \n return 0;\n}\n\n\n复杂度分析：\n\n该算法的时间复杂度为O(n^2)，空间复杂度为O(n)。