时间戳

首页 > 解决方案 > O(n^2) 算法找到最大的 3 个整数算术级数

c++ - O(n^2) 算法找到最大的 3 个整数算术级数

问题描述

问题相当简单。给定 N (3 <= N <= 3000) 个整数的输入，找出序列中 3 个整数算术级数的最大和。例如。(15, 8, 1) 是比 (12, 7, 2) 更大的算术级数，因为 15 + 8 + 1 > 12 + 7 + 2。最大算术级数之间的整数不必相邻，并且它们出现的顺序无关紧要。

一个示例输入是：

6
1 6 11 2 7 12

其中第一个数字是 N（在本例中为 6），第二行是长度为 N 个整数的序列。

并且输出将是任何 3 整数算术级数的最大和。像这样：

21

因为 2、7、12 是序列中任意 3 整数算术级数中和最大的，并且 2 + 7 + 12 = 21。也保证了序列中存在 3 整数算术级数。

编辑：构成总和（输出）的数字必须是一个算术级数（常数差），长度为 3 个整数。在样本输入的情况下，(1 6 11) 是一个可能的算术级数，但它小于 (2 7 12)，因为 2 + 7 + 12 > 1 + 6 + 11。因此将输出 21，因为它是更大。

这是我用 C++ 解决这个问题的尝试：

#include <bits/stdc++.h>
using namespace std;
vector<int> results;
vector<int> middle;
vector<int> diff;
int main(){
    int n;
    cin >> n;
    int sizes[n];
    for (int i = 0; i < n; i++){
        int size;
        cin >> size;
        sizes[i] = size;
    }
    sort(sizes, sizes + n, greater<int>());
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            int difference = sizes[i] - sizes[j];
            diff.insert(diff.end(), difference);
            middle.insert(middle.end(), sizes[j]);
        }
    }
    for (size_t i = 0; i < middle.size(); i++){
        int difference = middle[i] - diff[i];
        for (int j = 0; j < n; j++){
            if (sizes[j] == difference) results.insert(results.end(), middle[i]);
        }
    }
    int max = 0;
    for (size_t i = 0; i < results.size(); i++) {
        if (results[i] > max) max = results[i];
    }
    int answer = max * 3;
    cout << answer;
    return 0;
}

我的方法是使用单独的向量记录中间数字和差异，然后循环遍历向量并搜索中间数字减去差异是否在数组中，并将其添加到另一个向量中。然后找到最大的中间数并乘以 3 得到总和。这种方法使我的算法从 O(n^3) 变为大约 O(n^2)。但是，该算法并不总是每次都能产生正确的输出（我想不出一个不起作用的测试用例），并且由于我使用单独的向量，因此std::bad_alloc对于大 N 值会出现错误因为我可能使用了太多内存。这个问题的时间限制是每个测试用例 1.4 秒，内存限制是 64 MB。

由于 N 最多只能为 3000，因此 O(n^2) 就足够了。那么这个问题的最佳 O(n^2) 解决方案（或更好）是什么？

标签： c++algorithm

解决方案

因此，这个问题的一个简单解决方案是将所有元素放入 anstd::map以计算它们的频率，然后迭代等差数列中的第一个和第二个元素，然后在地图中搜索第三个元素。

迭代需要O(n^2)和映射查找，find()通常需要O(logn).

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

const int maxn = 3000;
int a[maxn+1];
map<int, int> freq;

int main()
{
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {cin >> a[i]; freq[a[i]]++;} // inserting frequencies

    int maxi = INT_MIN;
    for (int i = 1; i <= n-1; i++)
    {
        for (int j = i+1; j <= n; j++)
        {
            int first = a[i], sec = a[j]; if (first > sec) {swap(first, sec);} //ensure that first is smaller than sec
            int gap = sec - first; //calculating difference
            if (gap == 0 && freq[first] >= 3) {maxi = max(maxi, first*3); } //if first = sec then calculate immidiately
            else
            {
                int third1 = first - gap; //else there're two options for the third element
                if (freq.find(third1) != freq.end() && gap != 0) {maxi = max(maxi, first + sec + third1); } //finding third element
            }
        }
    }
    cout << maxi;
}

输出 ：21

另一个测试：

6
3 4 5 7 7 7

输出 ：21

另一个测试：

5
10 10 9 8 7

输出 ：27

您可以尝试std::unordered_map进一步降低复杂性。

另请参阅为什么是“使用命名空间 std;” 被认为是不好的做法？

推荐阅读