Choosing a Subarray 2
Time limit2sMemory limit128 MB
Find a contiguous subarray maximizing (sum of elements) times (minimum element), and output that maximum score with the interval bounds.
- Level
Medium6 of 10
- Topics
- Stack, Prefix sum, Array
- Solved
- No attempts yet
Problem
You are given a one-dimensional array A[1], ..., A[N] of length N (1 <= N <= 100,000).
Choose two integers i and j such that 1 <= i <= j <= N, forming the subarray A[i], ..., A[j]. The score of this subarray is defined as follows.
(A[i] + ... + A[j]) * min{A[i], ..., A[j]}
In other words, the score is the sum of the subarray multiplied by the minimum value inside that subarray.
Given A, write a program that finds the maximum possible score and prints an interval that achieves it.
Input
The first line contains the integer N.
The second line contains N integers representing A[1], ..., A[N]. Each integer is between 0 and 1,000,000, inclusive.
Output
Print the maximum possible score on the first line.
On the second line, print the start position i and end position j of an interval that achieves that score.