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)$