C++ 等差数列问题：最长等差数列长度 - 枚举算法

C++ 等差数列问题：最长等差数列长度 - 枚举算法

题目描述

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

输入格式

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

输出格式

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

输入输出样例内容:

输入样例1

5
1 2 3 4 5

输出样例1

5

输入样例2

6
1 2 3 5 6 7

输出样例2

3

时空限制

• CPU占用时长: 1秒
• 内存使用限制: 128MB

解题思路

可以使用枚举算法来解决这个问题。枚举所有可能的等差数列，并记录最长的等差数列的长度。

C++ 代码

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

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n); // 对数组排序，方便判断等差数列
    int maxLen = 1; // 初始化最长等差数列长度为1
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            int d = a[j] - a[i]; // 计算公差
            int len = 2; // 等差数列长度初始化为2
            int k = j + 1;
            while (k < n && a[k] == a[j] + d) { // 寻找下一个符合条件的数
                len++;
                k++;
            }
            maxLen = max(maxLen, len); // 更新最长等差数列长度
        }
    }
    cout << maxLen << endl;
    return 0;
}

代码解释

1. 输入数据：首先，从标准输入中读取 'n' 和 'n' 个数。
2. 排序：将数组排序，方便后续判断等差数列。
3. 枚举：使用两层循环枚举所有可能的等差数列的起点和终点。
4. 计算公差：计算两个数之间的差值，作为公差 'd'。
5. 寻找下一个数：使用 while 循环查找下一个符合等差数列条件的数。
6. 更新最长长度：如果当前等差数列长度大于最长长度，则更新最长长度。
7. 输出结果：输出最长等差数列的长度。

时间复杂度

时间复杂度为 O(n^2)，其中 'n' 是输入数组的长度。

优化建议

1. 可以使用哈希表来优化代码，将每个数出现的次数记录下来，这样可以更快地判断下一个数是否符合等差数列的条件。
2. 可以使用动态规划来解决这个问题，可以将时间复杂度降低到 O(n log n)。