5.1 暴力枚举

计算机解决问题的优势就在于能够快速执行大量重复计算。实际上，时间充足的情况下，暴力枚举每一种情况是最为可靠的算法。

例题：蓝桥 基础练习 数列特征

问题描述

给出n个数，找出这n个数的最大值，最小值，和。

输入格式

第一行为整数n，表示数的个数。

第二行有n个数，为给定的n个数，每个数的绝对值都小于10000。

输出格式

输出三行，每行一个整数。第一行表示这些数中的最大值，第二行表示这些数中的最小值，第三行表示这些数的和。

样例输入

5
1 3 -2 4 5

样例输出

5
-2
11

数据规模与约定

1 <= n <= 10000。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;    // n 的最大范围
int a[N];
int n;                    // 最初始读入的 n, m, t 等习惯开在全局
int main() {
    cin >> n;
    for (int i=0; i<n; ++i) {
        cin >> a[i];
    }
    int maxn = a[0], minn = a[0], sum = 0;    // 巧用第一个元素作为maxn, minn的初始值
    for (int i=0; i<n; ++i) {
        maxn = max(maxn, a[i]);
        minn = min(minn, a[i]);
        sum += a[i];
    }
    cout << maxn << endl << minn << endl << sum << endl;
    return 0;
}

C++ 的 algorithm 头文件提供了 max(), min(), swap() 等函数，无需自己实现。

对数组进行一次遍历即可完成。由于输入本身要读入 个数字，时间复杂度已经没有优化空间。但本题有一个空间优化，那就是数组其实并无必要，我们可以边读入边更新三个答案变量。这就是说，我们可以不必存下题目输入的所有数据。

这里只是为了展示不拘泥于题目的思路，对于此题如此操作并无必要。

参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4;
int a[N];
int n;
int main() {
    cin >> n;
    int maxn, minn, sum;
    cin >> maxn;
    minn = sum = maxn;    // 第 1 个数直接赋给 3 个变量
    // 从第二个数边读入边开始更新 3 个变量
    for (int i=1; i<n; ++i) {
        int x;
        cin >> x;
        maxn = max(maxn, x);
        minn = min(minn, x);
        sum += x;
    }
    cout << maxn << endl << minn << endl << sum << endl;
    return 0;
}

时间复杂度：#card=math&code=O%28n%29&id=jkXRk)