一个数组的 最小乘积 定义为这个数组中 最小值 乘以 数组的 和 。
比方说,数组 [3,2,5] (最小值是 2)的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。
给你一个正整数数组 nums ,请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大,请你返回答案对 109 + 7 取余 的结果。请注意,最小乘积的最大值考虑的是取余操作 之前 的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。
子数组 定义为一个数组的 连续 部分。
示例 1:
输入:nums = [1,2,3,2]
输出:14
解释:最小乘积的最大值由子数组 [2,3,2] (最小值是 2)得到。
2 * (2+3+2) = 2 * 7 = 14 。
思路:
遍历数组,每次以当前值K为区间最小值,乘以区间和得到最小乘积,记录最小乘积最大值.这个做法可以保证找到最大值.
考虑区间两侧,因为要找最小乘积的最大值而最小值已经确定,故希望区间长度越大越好(题目确定没有负数),故最远的左边界是第一个小于K的值的位置,右边界是向右看第一个小于K的值的位置.
故求区间边界转化为求左侧和右侧第一个小于K的值的位置,可用单调栈优化.
求区间和用前缀和优化.
typedef long long ll;
const int N = 100010;
int h[N], //单调栈
l[N], r[N], //li表示左侧第一个小于nums[i]的数的位置 ri类似
q[N];//队列内存点,需要左右端点的位置
ll s[N];
class Solution {
public:
int maxSumMinProduct(vector<int>& nums) {
int n = nums.size();
for (int i = 1; i <= n; ++i) {//从1开始
h[i] = nums[i - 1];//拷贝值
s[i] = s[i - 1] + h[i];//前缀和
}
h[0] = h[n + 1] = 0;//端点设0
int tt = 0;
q[0] = 0;
//正向遍历求左侧第一个
for (int i = 1; i <= n; ++i) {
while (h[i] <= h[q[tt]]) tt--;
l[i] = q[tt];
q[++tt] = i;
}
tt = 0;
q[0] = n + 1;
//反向遍历求右侧第一个
for (int i = n; i ; --i) {
while (h[i] <= h[q[tt]]) tt--;
r[i] = q[tt];
q[++tt] = i;
}
ll res = 0;
for (int i = 1; i <= n; ++i) {
res = max(res, h[i] * (s[r[i] - 1] - s[l[i]]));
}
return res % 1000000007;
}
};
https://www.nowcoder.com/questionTerminal/e6e57ef2771541dfa2f1720e50bebc9a
原题链接