C++ 等差数列 题解 - 6237 - 枚举算法

题目描述

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

输入格式

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

输出格式

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

输入输出样例内容

输入样例： 5 1 2 3 4 5

输出样例： 5

解题思路

首先，我们可以使用两重循环来枚举等差数列的起始位置和公差。假设我们选择的起始位置是 i，公差是 d，那么我们就可以确定一个等差数列，然后遍历数组，统计等差数列中的元素个数。在遍历数组时，我们可以使用一个哈希表来记录数组中的每个元素的个数，方便我们进行查找和更新。

具体实现

1. 读入 n 和数组 a。
2. 初始化一个哈希表 cnt，用于记录数组中每个元素的个数。
3. 初始化一个变量 res，用于记录最长等差数列的长度，初始值为 1。
4. 使用两重循环来枚举起始位置和公差。
   • 内层循环遍历数组，统计等差数列中的元素个数。
   • 更新 res 的值，取较大值。
5. 输出 res 的值。

C++代码实现

#include <iostream>
#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];
    }
    
    unordered_map<int, int> cnt;
    int res = 1;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int d = a[j] - a[i];
            cnt[a[j]] = 2;
            int k = a[j] + d;
            int len = 3;
            while (cnt.find(k) != cnt.end()) {
                cnt[k]++;
                len = max(len, cnt[k]);
                k += d;
            }
            res = max(res, len);
        }
    }
    
    cout << res << endl;
    
    return 0;
}