进阶 · 数组

数组最大值

读 N,再读 N 个数,输出最大的。把三个数的最大值的打擂台思路扩展到任意个数 — 一千道未来题目的原型。

一句话答案把 N 个数读进数组，用第一个元素作为运行最大值的初值 —— 用 0 初始化的话，全负数的数组会算错。

题目

输入: 第一行 N(1 ≤ N ≤ 1000);第二行 N 个整数。

输出: 其中最大的数。

样例:

输入输出
5
3 9 1 7 4		9
4
-3 -7 -1 -9		-1

你的解答

main.cpp — 你的解答
「运行我的输入」用的自定义输入

判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。

卡住了？提示

提示 1 — 两种都合法的架构

方案 A:全读进 int a[1000],再循环找最大。方案 B:根本不用数组 — 边读边打擂台(循环里 cin >> a;)。都能过;B 只用常数内存。知道什么时候不需要存数据,是真本事。

提示 2 — 擂台的初值

用第一个值当初值,别用 0 — 判题里有全负数的输入,0 初值会报出一个数据里根本不存在的数。(和三个数的最大值同款陷阱,这回有空间咬得更狠。)

题解（先自己试试！） 
#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int m, a;
    cin >> m;                 // 第一个值当擂主
    for (int i = 1; i < n; i++) {
        cin >> a;
        if (a > m) m = a;
    }
    cout << m << endl;
    return 0;
}

进阶目标:打印最大值的位置（更新时记住下标）,或者最小值和最大值都打,或者求和与平均 — 小心,平均数会踩整数除法的坑。下一关:奇偶统计。

深度解析

为什么这样做对

在数据流上打擂台只需要 O(1) 内存——数组根本不用留下来。这正是面试官想听到的那句洞察。

代价

O(n) 时间、O(1) 额外空间，尽管输入本身是 O(n)。

常见错法

  • 题目允许 1000 个数，你却开一个 100 的定长数组——这是等着爆栈。能流式就流式。
  • 要输出位置就得另开一个变量记下标。忘了更新会得到「值对、位置错」。

下一步

从比较换成计数：奇偶统计。

记住这两句

  • 打擂台不需要数组。
  • O(n) 时间不等于 O(n) 空间。
🐞 这段是错的 —— 点开,亲手让它挂一次

最大值初值写成 0，而不是第一个元素

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int best = 0;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        if (v > best) best = v;
    }
    cout << best << endl;
    return 0;
}