max值PK

题目描述

N个数的数组：a[1],a[2],...,a[N]。

将此数组分成前后2部分，a[1]...a[m]/a[m+1]...a[N]，满足1 <= m < N。

然后在这2部分中各自选出最大元素（假设前后部分最大值分别为maxA, maxB）进行PK，即计算maxA - maxB。

请问该如何选取m，使得|maxA - maxB|最大

输入格式

第1行包含一个整数N（N <= 2000000）

第2行包含N个int范围内的整数，空格隔开

输出格式

一个整数，表示|maxA - maxB|可以取到的最大值

样例 #1

样例输入 #1

4
2 1 4 3

样例输出 #1

2

时间限制：1秒 内存限制：125MB

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i ++ )cin >> a[i];
	vector<int> pre(n), suf(n);
	pre[0] = a[0];
	for (int i = 1; i < n; i ++ )pre[i] = max(pre[i - 1], a[i]);
	suf[n - 1] = a[n - 1];
	for (int i = n - 2; i >= 0; i -- )suf[i] = max(suf[i + 1], a[i]);
	int res = 0;
	for (int i = 1; i < n; i ++)res = max(res, abs(pre[i - 1] - suf[i]));
	cout << res << endl;
	return 0;
}