2019 ICPC南昌邀请赛比赛 I. Max answer （单调栈+思维预处理）

Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.

Now she is planning to find the max value of the intervals in her array. Can you help her?

Input

First line contains an integer n(1 \le n \le 5 \times 10 ^5n(1≤n≤5×105).

Second line contains nn integers represent the array a (-10^5 \le a_i \le 10^5)a(−105≤ai≤105).

Output

One line contains an integer represent the answer of the array.

样例输入复制

5
1 2 3 4 5

样例输出复制

大意就是让你获取区间和*区间最小值的最大是多少~

网上有一个类似的题目一样的题意，不过在那上面数据只有正数没有负数，所以，在满足某个数为最小的数的时候，直接调取之前所处理好的限定区间（在这个区间里认定的ai是最小的，可以通过单调栈O(n)获得）.但这里不同，存在负数就存在着很多需要考虑的问题，之前的处理好的区间也不再是正确的了~。

这里的话，我们先从双边进行遍历，分别获得ai左边的（包括这个点）的能够获取的最大的区间和，和最右边的（包括这个点）能够获取的最大的区间和。然后同样处理获得ai左边的（包括这个点）的能够获取的最小的区间和，和最右边的（包括这个点）能够获取的最小的区间和，那么我们就可以知道包含点ai的最大的区间和和最小的区间和是多少了~~。这样的话，ai*（最大的区间和）和ai*(最小的区间和)其中一个肯定是以为ai最小点能够获得的最大的所求值。

奥，补充一下，我们所获取的最大的区间和和最小的区间和可能超过了我们之前处理的限定区间，在这种情况下我们别忘了进行相减。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500010;
long long m[maxn];
long long sum[maxn], l[maxn], r[maxn];
long long zsum[maxn], zzsum[maxn];
long long fsum[maxn], ffsum[maxn];
int main() {
	ios::sync_with_stdio(0);
	int n;
	cin >> n;
	sum[0] = 0; 
	for (int i = 1; i <= n; i++) {
		cin >> m[i]; sum[i] = sum[i - 1] + m[i];
		l[i] = r[i] = i;
	}sum[n + 1] = sum[n];
	stack<int> s;
	int i = 1;
	while (i<=n) {
		if (s.empty() || m[i] > m[s.top()]) {
			s.push(i);
			++i;
		}
		else {
			l[i] = l[s.top()];
			s.pop();
		}
	}
	while (!s.empty())
		s.pop();
	i = n;
	while (i >= 1) {
		if (s.empty() || m[i] > m[s.top()]) {
			s.push(i);
			--i;
		}
		else {
			r[i] = r[s.top()];
			s.pop();
		}
	}


	long long su = 0, t = 0;
	for (int i = 1; i <= n; i++) {
		su += m[i];
		zsum[i] = su;
		if (t < l[i]) {
			zsum[i] -= sum[l[i] - 1] - sum[t];
		}
		if (su < 0) {
			su = 0;
			t = i;
		}
	}
	su = 0; t = n + 1;
	for (int i = n; i >= 1; i--) {
		su += m[i];
		zzsum[i] = su;
		if (t > r[i]) {
			zzsum[i] -= sum[t - 1] - sum[r[i]];
		}
		if (su < 0) {
			su = 0;
			t = i;
		}
	}
	// 负数开始。
	su = 0; t = 0;
	for (int i = 1; i <= n; i++) {
		su += m[i];
		fsum[i] = su;
	//	cout << su << " "<<t<<" "<<l[i]<<endl;
		if (t < l[i]) {
		//	cout << i <<" now: "<<sum[l[i]-1]<<" "<<sum[t]<< endl;
			fsum[i] -= sum[l[i] - 1] - sum[t];
		}
		if (su > 0) {
			su = 0;
			t = i;
		}
	}
	su = 0; t = n;
	for (int i = n; i >= 1; i--) {
		su += m[i];
		ffsum[i] = su;
		if (t > r[i]) {
			ffsum[i] -= sum[t - 1] - sum[r[i]];
		}
		if (su > 0) {
			su = 0;
			t = i;
		}
	}
	long long ans = -0x3f3f3f3f3f3f3f3f;
	for (int i = 1; i <= n; i++) {
		long long a = zsum[i] - m[i] + zzsum[i];
		long long b = fsum[i] - m[i] + ffsum[i];
		ans = max(m[i] * a, ans);
		ans = max(ans, m[i] * b);
	}
	cout << ans << "\n";
	return 0;
}