文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

一個(gè)數(shù)組的 最小乘積 定義為這個(gè)數(shù)組中 最小值 乘以 數(shù)組的 和 。

比方說(shuō)，數(shù)組 [3,2,5] （最小值是 2）的最小乘積為 2 * (3+2+5) = 2 * 10 = 20 。
給你一個(gè)正整數(shù)數(shù)組 nums ，請(qǐng)你返回 nums 任意 非空子數(shù)組 的最小乘積 的 最大值 。由于答案可能很大，請(qǐng)你返回答案對(duì) 10^9 + 7 取余 的結(jié)果。

請(qǐng)注意，最小乘積的最大值考慮的是取余操作 之前 的結(jié)果。
題目保證最小乘積的最大值在 不取余 的情況下可以用 64 位有符號(hào)整數(shù) 保存。

子數(shù)組 定義為一個(gè)數(shù)組的 連續(xù) 部分。

示例 1： 輸入：nums = [1,2,3,2] 輸出：14 解釋：最小乘積的最大值由子數(shù)組 [2,3,2] （最小值是 2）得到。 2 * (2+3+2) = 2 * 7 = 14 。示例 2： 輸入：nums = [2,3,3,1,2] 輸出：18 解釋：最小乘積的最大值由子數(shù)組 [3,3] （最小值是 3）得到。 3 * (3+3) = 3 * 6 = 18 。示例 3： 輸入：nums = [3,1,5,6,4,2] 輸出：60 解釋：最小乘積的最大值由子數(shù)組 [5,6,4] （最小值是 4）得到。 4 * (5+6+4) = 4 * 15 = 60 。提示： 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^7

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/maximum-subarray-min-product
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 為了求子數(shù)組的和，需要得到前綴和
• 為了求以每個(gè)數(shù)為最小值的子數(shù)組的兩端的極限位置（數(shù)字都大于0，越多越好），可以使用單調(diào)棧獲取
• 時(shí)間復(fù)雜度 $O(n)$

class Solution { public:int maxSumMinProduct(vector<int>& nums) {int n = nums.size();vector<long long> presum(n);for(int i = 0; i < n; i++)presum[i] = (i > 0 ? presum[i-1] : 0) + nums[i];//前綴和vector<int> left(n, 0), right(n, n-1);//每個(gè)位置為最小值的情況下，區(qū)間左右極限位置stack<int> s;for(int i = 0; i < n; i++)//順序遍歷，求左邊界限{while(!s.empty() && nums[i] <= nums[s.top()])s.pop();//左邊比我大，我是最小的if(!s.empty())left[i] = s.top()+1;//左邊比我小了，我不是最小的，左邊界是 棧頂?shù)闹?#43;1位置s.push(i);}while(!s.empty())s.pop();for(int i = n-1; i >= 0; i--)//逆序遍歷求右邊界{while(!s.empty() && nums[i] <= nums[s.top()])s.pop();//右邊比我大，我是最小的if(!s.empty())right[i] = s.top()-1;//右邊有比我小的，我不是最小的，右邊界是 棧頂?shù)闹?1位置s.push(i);}long long ans = 0;for(int i = 0; i < n; i++){int l = left[i], r = right[i];//左右邊界ans = max(ans, (presum[r]-(l>0?presum[l-1]:0))*nums[i]);}return ans%(1000000007);} };

280 ms 88 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1856. 子数组最小乘积的最大值（前缀和 + 单调栈）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。