week2-[一维数组]最大元素

week2-[一维数组]最大元素

题目描述

给定 $N$ 个整数$A_1,A_2,\dots ,A_N$。请求出这 $N$ 个数的最大值，并找出最大值的出现位置（$A_1$ 的位置为 $1$，$A_2$ 的位置为2，依此类推）。如果同时存在多个最大的数，按从小到大的顺序输出最大的数出现的所有位置。

输入格式

读入包括 $2$ 行。第一行只有 $1$ 个整数 $N$，表示数的个数。第二行包括 $N$ 个整数 $A_1,A_2,\dots ,A_N$。

输出格式

输出 $2$ 行，第一行包括一个整数，表示 $A_1,A_2,\dots ,A_N$ 的最大值。 第二行包含若干个整数，表示最大值在 $A_1,A_2,\dots ,A_N$ 中的所有出现位置（每两个数之间用恰好一个空格隔开）。

样例 #1

样例输入 #1

8
1 3 5 9 2 6 4 2

样例输出 #1

9
4

样例 #2

样例输入 #2

9
2 5 2 6 8 5 11 3 11

样例输出 #2

11
7 9

样例 #3

样例输入 #3

5
10 10 10 8 10

样例输出 #3

10
1 2 3 5

提示

样例解释1

$1,3,5,9,2,6,4,2$ 中的最大值为 $9$，出现在第 $4$ 个位置。

样例解释2

$2,5,2,6,8,5,11,3,11$ 中的最大值为 $11$，出现在第 $7$ 个位置和第 $9$ 个位置。

样例解释3

$10,10,10,8,10$ 中的最大值为 $10$，出现在第 $1,2,3,5$ 个位置。

数据范围

对于所有数据，$1\le N\le 500,-100\le A_i\le 100$。

1. 阅读题目

• 输入：
  • 第 1 行：整数 $N$
  • 第 2 行：$N$ 个整数 $A_1,A_2,\dots ,A_N$
• 输出：
  1. 第一行：最大值
  2. 第二行：最大值出现的所有位置（从 1 开始），按出现顺序输出

2. 分析问题

思路很直接：

1. 初始化 maxVal = A[0]，pos 空数组保存位置。
2. 遍历数组：
   • 如果当前元素 > maxVal → 更新 maxVal，清空 pos，记录当前位置
   • 如果当前元素 == maxVal → 在 pos 追加当前位置
3. 输出 maxVal 和 pos

注意事项：

• 位置从 1 开始，所以索引 i+1 保存到 pos。
• 数据量小（$N\le 500$），可以直接用数组保存位置。

3. C++ 代码实现（兼容低版本）

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;

    int A[505];      // 保存输入数组
    int pos[505];    // 保存最大值出现的位置
    int maxVal = -101; // 初始小于最小可能值
    int cnt = 0;     // 记录最大值出现次数

    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (A[i] > maxVal) {
            maxVal = A[i];
            cnt = 1;
            pos[0] = i + 1; // 保存位置，从1开始
        } else if (A[i] == maxVal) {
            pos[cnt] = i + 1;
            cnt++;
        }
    }

    // 输出最大值
    cout << maxVal << "\n";

    // 输出所有位置
    for (int i = 0; i < cnt; i++) {
        if (i > 0) cout << " ";
        cout << pos[i];
    }
    cout << "\n";

    return 0;
}

4. 示例运行

输入：

9
2 5 2 6 8 5 11 3 11

输出：

11
7 9

✅ 总结

• 遍历数组同时统计最大值和位置
• 出现新最大值时清空位置数组
• 相同最大值追加位置
• 时间复杂度 $O(N)$，空间复杂度 $O(N)$