题目描述
每年的 1024 程序员节日，黑马程序员都会举办大型的庆祝活动。今年的程序员节也不例外，每个班级的同学都发了橙子。
班级里有 n 名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第 i 名同学的成绩是 ai。班主任想根据同学们上个阶段的考试成绩来评定发橙子的数量。为了激励成绩优秀同学，发橙子时需要满足如下要求：
相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样，则它们分到的数量必须平等。
每个同学至少分配一个橙子
由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。请问，至少需要准备多少橙子呢？
输入
第一行是一个不超过 10^6 正整数 n，表示学生数量。
接下来一行有 n 个不超过 10^9 的非负整数 ai，表示第 i 个同学的成绩。
输出
输出答案，也就是需要最少准备多少个橙子。
样例输入
5
3 4 5 4 3
样例输出
9
分别从左到右和从右到左遍历一次数组，以从左到右的顺序为例
如果a[i]<a[i+1],就让L[i+1]=L[i]+1,类似于差分数组的样子。如果等于就相等，如果大于就附为0
R数组也一样的赋值
最后这一位等于L和R的最大值+1
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxx=1e6+100;
int a[maxx];
int L[maxx],R[maxx];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
L[1]=R[n]=0;
for(int i=2;i<=n;i++) {
if(a[i]>a[i-1]) L[i]=L[i-1]+1;
else if(a[i]==a[i-1]) L[i]=L[i-1];
else L[i]=0;
}
for(int i=n-1;i>=1;i--) {
if(a[i]>a[i+1]) R[i]=R[i+1]+1;
else if(a[i]==a[i+1]) R[i]=R[i+1];
else R[i]=0;
}
ll sum=0;
for(int i=1;i<=n;i++) sum+=max(L[i],R[i])+(ll)1;
cout<<sum<<endl;
return 0;
}
