题目链接：问题 1940 | 程序设计在线评测平台 (ldu.edu.cn)

题目描述

叶妍霜正在研究一个关于人类情感的数学理论，她最近的研究是将每一天的情感值以一个非负整数表示为一个数组序列arr[]，现在她要找出一个区间[L,R]，使得(arr[L]＋…＋arr[R])×arr[k]的值最大，其中arr[k]为区间[L,R]中的最小值。

输入描述

第一行为一个整数N，表示有N个（1≤N≤100000)情感值，第二行为N个情感值（ 0到10^6之间）。

输出描述

第一行为最大值，第二行为L和R的位置。、

---

可以把这个问题抽象为求最大矩形面积，我们把arr[i]看作一个边长为arr[i]的正方形，那么对于区间[L,R]中的最小值就可以看成是区间可以构建矩形的最大高。构建单调不递减栈来实现这个问题的求解。

#include<bits/stdc++.h>
using namespace std;

#define Pqueue priority_queue
#define lc p<<1
#define rc p<<1|1
#define IOS ios::sync_with_stdio(false),cin.tie(0);
#define fi first
#define se second

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> PII;

const int mod = 1000000007;
const int N = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll P = 131;

stack<ll> num, pos, len;
// num-单调不降栈   pos-位置栈   len-矩形长度栈
int arr[N], l, r;
ll n, mx;

/*void DEbug(stack<ll>& s) {
	stack<ll> tmp;
	while (!s.empty())
		tmp.push(s.top()), s.pop();
	while (!tmp.empty()) {
		cout << tmp.top() << " ";
		s.push(tmp.top());
		tmp.pop();
	}
	cout << "\n";
}*/
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	arr[n + 1] = -1;//arr>=1 -1<=arr
	for (int i = 1; i <= n+1; i++) {//n+1使得栈置空
		ll tmp = 0;					//记录长度
		int L = i;					//记录位置
		while (!num.empty() && arr[i] <= num.top()) {
			tmp += len.top();
			if (mx < tmp * num.top()) {
				mx = tmp * num.top();
				r = i - 1;			//r为i-1位
				l = pos.top();		//l为pos顶部
				//cout<<i<<" ";
				//DEbug(pos);
				//DEbug(num);
			}
			L=pos.top();			//更新最左边界
			pos.pop();
			num.pop();
			len.pop();				//出栈
		}
		pos.push(L);
		num.push(arr[i]);
		len.push(tmp + arr[i]);		//入栈
	}
	cout << mx << "\n" << l << " " << r;
}

int main() {
	IOS
	int T = 1;
	//cin>>T;
	while (T--)
		solve();
	return 0;
}

/*
oxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxox
x                                                                                      o
o       _/_/_/_/                                                              _/       x
x      _/                                                                              o
o     _/_/_/_/ _/  _/_/   _/_/   _/_/_/ _/_/   _/_/_/     _/_/    _/_/_/    _/ _/   _/ x
x    _/       _/_/     _/    _/ _/   _/   _/  _/    _/ _/    _/  _/    _/  _/   _/ _/  o
o   _/       _/       _/    _/ _/   _/   _/  _/    _/ _/    _/  _/    _/  _/    _/_/   x
x  _/       _/         _/_/   _/   _/   _/  _/_/_/     _/_/ _/ _/    _/  _/      _/    o
o                                          _/                           _/      _/     x
x                                         _/                        _/_/       _/      o
o                                                                                      x
xoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxoxo
*/