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

**题目描述:**

给定 n 个数，从中找出尽可能多的数使得他们能够组成一个等差数列.求最长的等差数列的长度.

**输入格式:**

第一行是一个整数 n ,接下来一行包括了 n 个数。

**输出格式:**

对于每个输入数据,输出你所找出的最长等差数列的长度

**输入输出样例内容:**

输入样例：

5
1 3 5 7 9

输出样例：

5

**解题思路:**

首先将输入的数存储在一个数组中，然后对数组进行排序。然后使用两层循环，外层循环遍历数组，内层循环从当前位置开始，计算当前位置和后面的数构成的等差数列的长度，并更新最大长度。最后输出最大长度。

以下是 C++ 的实现代码：

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
int nums[n];
for (int i = 0; i < n; i++) {
cin >> nums[i];
}
sort(nums, nums + n);
int maxLength = 0;
for (int i = 0; i &lt; n - 1; i++) {
    int diff = nums[i + 1] - nums[i];
    int length = 2;
    for (int j = i + 2; j &lt; n; j++) {
        if (nums[j] - nums[j - 1] == diff) {
            length++;
        } else {
            break;
        }
    }
    maxLength = max(maxLength, length);
}

cout &lt;&lt; maxLength &lt;&lt; endl;

return 0;

}

时间复杂度分析:

排序的时间复杂度为 O(nlogn)，遍历数组的时间复杂度为 O(n^2)，所以总的时间复杂度为 O(n^2logn)。空间复杂度为 O(n)。