maximum-subarray-min-product

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

The min-product of an array is equal to the minimum value in the array multiplied by the array&#39;s sum.

<ul>
	<li>For example, the array <code>[3,2,5]</code> (minimum value is <code>2</code>) has a min-product of <code>2 * (3+2+5) = 2 * 10 = 20</code>.</li>
</ul>

Given an array of integers <code>nums</code>, return the maximum min-product of any non-empty subarray of <code>nums</code>. Since the answer may be large, return it modulo <code>109 + 7</code>.

Note that the min-product should be maximized before performing the modulo operation. Testcases are generated such that the maximum min-product without modulo will fit in a 64-bit signed integer.

A subarray is a contiguous part of an array.

&nbsp;
Example 1:

<pre>
Input: nums = [1,2,3,2]
Output: 14
Explanation: The maximum min-product is achieved with the subarray [2,3,2] (minimum value is 2).
2 * (2+3+2) = 2 * 7 = 14.
</pre>

Example 2:

<pre>
Input: nums = [2,3,3,1,2]
Output: 18
Explanation: The maximum min-product is achieved with the subarray [3,3] (minimum value is 3).
3 * (3+3) = 3 * 6 = 18.
</pre>

Example 3:

<pre>
Input: nums = [3,1,5,6,4,2]
Output: 60
Explanation: The maximum min-product is achieved with the subarray [5,6,4] (minimum value is 4).
4 * (5+6+4) = 4 * 15 = 60.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 107</code></li>
</ul>

maxSumMinProduct

Maximum Subarray Min-Product

Subarray With Elements Greater Than Varying Threshold

subarray-with-elements-greater-than-varying-threshold

元素值大于变化阈值的子数组

Stack

Array

Prefix Sum

Monotonic Stack

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

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

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

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

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

 

示例 1：

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

示例 2：

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

示例 3：

<pre>
输入：nums = [3,1,5,6,4,2]
输出：60
解释：最小乘积的最大值由子数组 [5,6,4] （最小值是 4）得到。
4 * (5+6+4) = 4 * 15 = 60 。
</pre>

 

提示：

<ul>
	<li><code>1 <= nums.length <= 105</code></li>
	<li><code>1 <= nums[i] <= 107</code></li>
</ul>