[TIOJ] 1368. Get High!!

題目連結:http://tioj.infor.org/problems/1368

---

我這題想了好久好久，然後某天突然感覺這題可以這樣做XD
這題我的作法是，找到對於每一個元素，往左跟往右找到第一個比他小的數字，以兩者為範圍，算high值，最後再取max即。，而往又跟往左找第一個比他小的數字其實一個stack就可以做到了，只要維護stack裡由底往上是遞增就好。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<int,int> PII;
#define FF first
#define SS second

const int N = 100000 + 5;

lld arr[N], preS[N];
int rr[N], ll[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++) cin>>arr[i];
		arr[n+1]=0;
		for(int i=1;i<=n;i++) preS[i] = preS[i-1]+arr[i];
		stack<int> ss;
		for(int i=1;i<=n;i++){
			while(!ss.empty() and arr[ss.top()] > arr[i]){
				rr[ss.top()]=i-1;
				ss.pop();
			}
			ss.push(i);
		}
		while(!ss.empty()){
			rr[ss.top()]=n;
			ss.pop();
		}
		for(int i=n;i>=1;i--){
			while(!ss.empty() and arr[ss.top()] > arr[i]){
				ll[ss.top()]=i;
				ss.pop();
			}
			ss.push(i);
		}
		while(!ss.empty()){
			ll[ss.top()]=0;
			ss.pop();
		}
		lld high=0;
		PII pos;
		for(int i=1;i<=n;i++){
			lld h=(preS[rr[i]] - preS[ll[i]])*arr[i];
			if(h > high){
				pos={ll[i], rr[i]};
				high=h;
			}
		}
		cout<<high<<'\n'<<pos.FF+1<<' '<<pos.SS<<'\n';
	}
	return 0;
}