7-1 求最大值及其下标 (20 分)

题目描述：

给定一个长度为n的整数序列a1,a2,…,an，求出其中的最大值以及它在序列中的下标。

输入格式：

第一行包含整数n。

第二行包含n个整数，表示整数序列。

输出格式：

共一行，包含两个整数，分别表示最大值及其下标（下标从1开始）。

样例输入：

5
1 3 2 4 5

样例输出：

5 5

算法1：

(暴力枚举) $O(n)$

暴力枚举，遍历整个序列，记录最大值及其下标。

时间复杂度

遍历整个序列，时间复杂度为O(n)。

C++ 代码

算法2：

(分治) $O(nlogn)$

将序列分为两部分，分别求出左右两部分的最大值及其下标，然后比较两部分的最大值，返回较大的那个。

时间复杂度

每次将序列分为两部分，时间复杂度为O(logn)，共分logn次，每次比较两部分的最大值，时间复杂度为O(1)，总时间复杂度为O(nlogn)。

C++ 代码

算法3：

(线性扫描) $O(n)$

遍历整个序列，记录最大值及其下标。

时间复杂度

遍历整个序列，时间复杂度为O(n)。

C++ 代码