题目网站：http://class.51nod.com/Challenge/Problem.html#problemId=1272
一、题目描述
给出一个长度为N的整数数组A，对于每一个数组元素，如果他后面存在大于等于该元素的数，则这两个数可以组成一对。
每个元素和自己也可以组成一对。例如：{5, 3, 6, 3, 4, 2}，可以组成11对，如下（数字为下标）：
(0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5)。其中(1, 4)是距离最大的一对，距离为3。
输入描述
第1行：1个数N，表示数组的长度(2 <= N <= 50000)。
第2 - N + 1行：每行1个数，对应数组元素Ai(1 <= Ai <= 10^9)。
输出描述
样例输入
样例输出
二、解题思路
这道题发明了一个方法（也可以用单调栈 / 单调队列来做），我自己起了个名字叫做 “ 前缀累加 ” 。
这个方法也不能叫做方法吧，但可以称之为技巧。
能作为这两个数中的前一个数要满足的要求：前面没有小于他的，要不然答案还可以扩大
（我们把能满足这个要求的所有数字都存到A数组里）
能作为这两个数中的后一个数要满足的要求：后面没有大于他的，要不然答案还可以扩大
（我们把能满足这个要求的所有数字都存到B数组里）
相信大家读题的时候也已经发现了，我们要找的是他后面所有比这个数大于或等于的数。
我们不能比较附近挨着的两个，我们得把所有的都比较一遍，我给大家建议的方法就是：
一边输入也可以一边找出A数组中存什么数字好，输入完了后我们可以从N-1 —> 0 在来一次循环找出B数组里的数
至于怎么找呢？
我们可以记录下A数组里上一个数的下标，把 a[这个数] 和现在这个数进行比较，如果现在这个数小于上次存的那个数
A数组里多存一个i（我往A数组里存的都是下标），上次那个数的下标变成这次的下标。
B数组同理。不解释了
这时候，A数组里肯定是降序的，B数组肯定也是降序的，这点不解释了。
现在开始讲输出：
输出照常来说我们都要把A数组里的数和B数组里的数一一进行对比才能肯定哪个就是答案
可是这里我们用了一个小技巧：
假设A数组里有3个数，B数组里有3个数，正常情况来说需要判断9次，实际上这个代码可能只需要判断5次就出结果了。
而且正常情况还会TLE（超出时间限制）
那么我们这个不同寻常的技巧是什么？
首先我们肯定得判断A数组里的数肯定是得小于B数组里的数才可以的，ans取一个最大值（ans和这次的答案）
由于A数组是降序的，如果现在这个A数组里的数是小于B数组里的数，
A数组如果再往前一点（因为前面的数肯定比现在这个数要小）判断一下，如果可以的话肯定距离更大
如果ans没有重新赋值，（也就是说A数组里的数比B数组里的数大）B数组的数要往前一点，看看前面的数可不可以
三、代码描述
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long n, a[50010], A[50010], B[50010];
long long cnt_a=1, cnt_b=1, ans, prenum, postnum;
int main(){
cin >> n;
for(int i = 0;i < n;i++){
cin >> a[i];
if(prenum == 0 || a[i] < a[A[prenum-1]]){
A[prenum++] = i;
}
}
for(int i = n-1;i >= 0;i--){
if(postnum == 0 || a[i] > a[B[postnum -1]]){
B[postnum++] = i;
}
}
long long pre_idx = 0, post_idx = postnum -1;
for(;pre_idx < prenum && post_idx >= 0;){
if(a[A[pre_idx]] <= a[B[post_idx]]){
ans = max(B[post_idx] - A[pre_idx], ans);
--post_idx;
}else{
++pre_idx;
}
}
cout << ans << endl;
return 0;
}
51nod 1272 最大距离
原文：https://www.cnblogs.com/elisa02/p/13263452.html
