Maximum Min-Sum Product

★★★★★

3.3

7 votes

Stack, Advanced Data Structures, Sparse Table, Sparse table, Data Structures

Details

Submissions

Discussion

Editorial

Problem

Given an Array $arr$ of Integers having length $N$ , find the maximum value of $min(A[i, j]) \times sum(A[i,j])$ for all $0 \le i \le j < N$ where $A[i,j]$ denotes the non-empty subarray $[A_i, A_{i+1}, A_{i+2}, ..., A_{j-1}, A_j]$ .

Since the product may be large, return the product modulo $10^9 + 7$ .

Note:

Testcases are generated such that the maximum product without modulo will fit in a 64-bit signed integer.

Input Format:

First line contains an integer $T$ , the number of test cases.
First line of each testcase contains an integer $N$ , the length of array.
Second line of each testcase contains $N$ space seperated integers, the values of array.

Output Format:

For each testcase, output an integer, the maximum value of $min(A[i, j]) * sum(A[i,j])$ across all subarrays modulo $10^9 + 7$ .

Constraints:

$1 \le T \le 10$
$-10^5 \le A_i \le 10^5$
$1 \le N \le 10^5$

Sample Input

3
5
1 5 1 3 1
5
0 -1 -3 -1 0
6
-1 -5 -1 3 1 3

Sample Output

25
15
35

Time Limit: 5.5

Memory Limit: 256

Source Limit:

Explanation

In First Test Case, $arr = [1, 5, 1, 3, 1]$ , $arr[2,2] = [5]$ , and $min([5]) \times sum([5]) = 25$
In Second Test Case, $arr = [0, -1, -3, -1, 0]$ , and $min(arr) \times sum(arr) = -3 \times -5 = 15$
In Third Test Case, $arr = [-1, -5, -1, 3, 1, 3]$ , $arr[1,3] = [-1, -5, -1]$ , and $min([-1, -5, -1]) \times sum([-1, -5, -1]) = -5 \times -7 = 35$

Contributers:

Abhishek Choudhary

Geetartha Kaustav