练47.3 谁是老大

解题思路

递归函数maxPrefix(k)表示前k个数的最大值。k=1返回首项，其余返回max(maxPrefix(k-1),第k项)。

正确性说明

按顺序完成所述运算后，每个输入元素都被处理在相应位置或统计项中。保存的中间状态与已处理数据对应，最终输出与题目定义一致。

易错点

使用递归；输出中文前缀。

复杂度

固定5层，时间O(1)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

long long maxPrefix(const vector<long long> &a, int k) {
    if (k == 1)
        return a[0];
    return max(maxPrefix(a, k - 1), a[k - 1]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<long long> a(5);
    for (auto &x : a)
        cin >> x;
    cout << "最大的数是：" << maxPrefix(a, 5) << "\n";
    return 0;
}