Choosing a Subarray
Time limit2sMemory limit128 MB
Given an array, find the contiguous subarray that maximizes the product of its sum and its minimum element.
- Level
Medium6 of 10
- Topics
- Stack, Prefix sum, Divide and conquer
- Solved
- No attempts yet
Problem
There is a one-dimensional array A[1], ..., A[N] of size N (1 <= N <= 100,000).
For indices i and j with 1 <= i <= j <= N, the score of the subarray from i to j is
(A[i] + ... + A[j]) * min(A[i], ..., A[j]).
In other words, the score is the sum of the chosen subarray multiplied by the minimum value inside that subarray.
Given the array, find the maximum possible score among all contiguous subarrays.
Input
The first line contains the integer N.
The second line contains the integers A[1], ..., A[N]. Each integer is nonnegative and does not exceed 1,000,000.
Output
Print the maximum score on the first line.
Hint
If i = 3 and j = 5, the score is (6 + 4 + 5) * 4 = 60.