1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int maxSumMinProduct(vector<int>& nums) {
const int n = nums.size();
vector<long long> sum(n + 1);
for (int i = 0; i < n; ++i)
sum[i + 1] = sum[i] + nums[i];
vector<int> pre(n), next(n);
pre[0] = -1;
for (int i = 1; i < n; ++i) {
int j = i - 1;
while (j >= 0 && nums[j] >= nums[i])
j = pre[j];
pre[i] = j;
}
next[n - 1] = n;
for (int i = n - 2; i >= 0; --i) {
int j = i + 1;
while (j < n && nums[j] >= nums[i])
j = next[j];
next[i] = j;
}
long long ans = 0;
for (int i = 0; i < n; ++i)
ans = max(ans, nums[i] * (sum[next[i]] - sum[pre[i] + 1]));
return ans % static_cast<int> (1e9 + 7);
}
};
|