AOI Troublesome Frog

frog.cpp

#include <fstream>
using namespace std;
#define MAXN 100000

ifstream fin ("frogin.txt");
ofstream fout ("frogout.txt");

int N, h[MAXN], best=0, dpl[MAXN]={0}, dpr[MAXN]={0};


int main(){

	fin>>N;
	for(int i=0; i<N; ++i) fin>>h[i];

	best = h[0];
	for(int l=0; l<N; ++l){
		if(h[l]<best) best=h[l];
		dpl[l]=best;
	}
	
	best = h[N-1];
	for(int r=N-1; r>=0; --r){
		if(h[r]<best) best=h[r];
		dpr[r]=best;
	}

	best=0;
	for(int m=1; m<N-1; ++m){
		if( h[m]>dpl[m-1] && h[m]>dpr[m+1] && h[m]-dpl[m-1] + h[m]-dpr[m+1] > best)
			best = h[m]-dpl[m-1] + h[m]-dpr[m+1];
	}

	fout<<best<<endl;
	return 0;
}