当前位置：首页 > news >正文

算法随笔_59: 子数组最小乘积的最大值

news 来源：原创 2025/9/16 17:33:58

上一篇:算法随笔_58: 队列中可以看到的人数-CSDN博客

=====

题目描述如下:

一个数组的 最小乘积 定义为这个数组中 最小值 乘以数组的和。

比方说，数组 [3,2,5] （最小值是 2）的最小乘积为 2 * (3+2+5) = 2 * 10 = 20 。

给你一个正整数数组 nums ，请你返回 nums 任意 非空子数组 的最小乘积 的 最大值 。由于答案可能很大，请你返回答案对 10**9 + 7 取余的结果。

请注意，最小乘积的最大值考虑的是取余操作之前的结果。题目保证最小乘积的最大值在 不取余 的情况下可以用 64 位有符号整数 保存。

子数组 定义为一个数组的连续部分。

示例 1：

输入：nums = [1,2,3,2]
输出：14
解释：最小乘积的最大值由子数组 [2,3,2] （最小值是 2）得到。
2 * (2+3+2) = 2 * 7 = 14 。

=====

算法思路:

由于任意一个子数组的最小值必然是原数组中的某一个元素，因此我们可以把以某一个元素nums[i]为最小值的所有子数组都找出来，我们设这些数组的集合为set[i]。我们先找出set[i]的最小乘积的最大值score[i]。然后，再取所有score[i]的最大值即为本题的答案。

那score[i]怎么找呢？因为nums[i]的值是固定的，且题目提到原数组都是正数，因此我们需要向nums[i]的左右两侧尽可能的扩展，这样才能找到最大的数组和。一直要扩展到出现比nums[i]小的数nums[j]时为止。当然扩展的区间里不能包含nums[j]。

那么如何高效的找出nums[i]的最大左边界呢？

上面提到一直要扩展到出现比nums[i]小的数nums[j]时为止。我们可以通过维护一个单调栈stck来完成所有nums[i]的最大左边界的统计。我们设数组lEdge存储每个元素的最大左边界。数组rEdge存储最大右边界。

我们从左往右枚举原数组，当数值不断递增时，我们把nums[i]加入stck。lEdge[i]就等于i。因为nums[i]的左侧是比它小的数。nums[i]的最大左边界就是它本身。

当数值nums[i]下降或相等时，我们不断弹出栈顶元素stck[-1]，直到碰到小于nums[i]的元素，那么lEdge[i]就等于当前的stck[-1]+1。加1，表示我们要取最后一个弹出的下标值才是最大左边界。如果stck为空，那么lEdge[i]就等于0，即，数组的起始处。

枚举完所有元素后，就统计出了所有的最大左边界。同理，我们从右往左，可以统计出所有元素的最大右边界，并存入rEdge。

完成所有的左右边界计算后，我们就可以计算出所有的score[i]。最大的score[i]即为最终答案。注意最后的答案要 10**9 + 7 取余。

由于每个元素只会入栈和出栈一次，所以时间复杂度为O(n) 。下面是代码实现:

class Solution(object):def maxSumMinProduct(self, nums):""":type nums: List[int]:rtype: int"""nums_len=len(nums)lEdge=[0]*nums_lenrEdge=[0]*nums_lenpre_sum=[0]*nums_lenstck=[]for i in range(nums_len):while stck and nums[i] <= nums[stck[-1]]:stck.pop()lEdge[i]=stck[-1]+1 if stck else 0stck.append(i)pre_sum[i]=pre_sum[i-1]+nums[i] if i>0 else nums[i]stck=[]for i in range(nums_len-1, -1, -1):while stck and nums[i] <= nums[stck[-1]]:stck.pop()rEdge[i]=stck[-1]-1 if stck else nums_len-1stck.append(i)res=0for i in range(nums_len):tmpRes=nums[i] * (pre_sum[rEdge[i]]-pre_sum[lEdge[i]]+nums[lEdge[i]])res=max(res, tmpRes)res=res%(10**9+7)return res

关键词: 单调栈

相关文章：