Interval value (monotone stack)

Given an array sequence , You need to find an interval , Make this interval the largest of all the intervals calculated as follows ：

The smallest decimal in the interval * The sum of all numbers in the interval and the maximum value of the final program output after calculation , There is no need to output a specific interval . If a given sequence [6 2 1] Then according to the above formula , You can get all the calculated values of each selected interval :

[6] = 6 * 6 = 36;

[2] = 2 * 2 = 4;

[1] = 1 * 1 = 1;

[6,2] = 2 * 8 = 16;

[2,1] = 1 * 3 = 3;

[6, 2, 1] = 1 * 9 = 9;

It can be seen from the above calculation [6] , The calculated value is 36, Then the program output is 36.

All numbers in the interval are in [0, 100] Within the scope of ;

Input description :
The first line is the length of the array sequence n, The second line inputs the array sequence .
about 50% The data of , 1 <= n <= 10000;
about 100% The data of , 1 <= n <= 500000;

Output description :
The calculated maximum value of the output array .

Input example 1:
3
6 2 1

Output example 1:
36

Answer key ：
First of all, it is clear how to calculate the maximum value of the interval we require , In fact, according to the way of enumeration calculation , We can further generalize , If the 6 Is the minimum value of the interval , Then this interval can take [6], The interval value is 36; With 2 Is the minimum value of the interval , Then this interval can take [2], [6, 2], The maximum interval value of these two intervals is [6, 2] The value is 12; With 1 Is the minimum value of the interval , Then this interval can take [1], [2, 1], [6, 2, 1], The maximum value of these three intervals is [6, 2, 1] The value is 9, There is no need to calculate [1], [2, 1], Because it must be better than 2 The calculated value of the longest interval that is the minimum value is smaller ; Finally, the maximum value of all intervals is 36.

It can be seen that the main problem is the minimum value of enumeration interval , Then determine how to find the longest interval range with the minimum value of the current enumerated interval （ Only the longest interval satisfied by the minimum value of the current enumeration , At this time, the maximum value of the interval obtained according to the calculation rules , Is the maximum value in all intervals satisfied by the minimum value of the current enumeration ）.

Based on the above ideas ：

• The main calculation rules ： The smallest number of intervals x The sum of all numbers in the interval
• Using monotone stack to solve this problem , First, enumerate all the elements to be the minimum number in the interval , Next, find the left side of the interval 、 Right border , Use a monotonically increasing stack to store its left 、 The position of the right boundary , For the top element in the incremental stack , The last element at the top of the stack must be smaller than the element at the top of the stack , That is, the left boundary of the interval is the next element at the top of the stack （ The interval does not contain this element ）. For the elements of the right boundary of the interval , If the current height value of the enumeration is less than the top of the stack element , At this point, it indicates that the right boundary of the top element of the stack is found （ The interval does not contain this element ）. Otherwise, the height of the enumeration will be put on the stack , Then continue to look for elements smaller than the top element of the current stack . So for the stack top element , We can always determine the left and right boundaries of the interval , Then calculate the minimum number of the interval x The sum of all numbers in the interval .

In the following implementation , Monotonically increasing the index of the position of the storage interval in the stack ：

n = int(input())
data = list(map(int, input().split()))
stack = []  #  Incremental stack 
#  Add sentinels 0, The main purpose is to prevent the remaining elements in the stack from being processed 
#  For example, the following elements are incremental , It's going to keep going up the stack , At this point, there are still remaining height elements in the stack , Therefore, it is necessary to perform 1 Secondary cycle .
data.append(0)  
res = 0
for i, num in enumerate(data):
    while stack and num < data[stack[-1]]:  #  Find the highest point 
        loc = stack.pop(-1)
        begin = stack[-1]+1 if stack else 0
        res = max(res, data[loc]*sum(data[begin:i]))
    stack.append(i)  #  Index of records 
print(res)

The following is the implementation code with two sentinels added

n = int(input())
data = list(map(int, input().split()))
stack = []  #  Incremental stack 

#  Add sentry here , Mainly for the subsequent calculation of width , utilize i - stack[-1] - 1 Calculation , Add... On the left 0 It can avoid the situation that the stack is empty and cannot be calculated , Because there is always a... At the bottom of the stack 0.
#  Add one on the right 0 To avoid remaining height in the stack , For example, the following elements are incremental , It's going to keep going up the stack , At this point, there are still remaining height elements in the stack , Therefore, it is necessary to perform 1 Secondary cycle .

data = [0] + data + [0]
res = 0
for i, num in enumerate(data):
    while stack and num < data[stack[-1]]:  #  Find the highest point 
        loc = stack.pop(-1)
        begin = stack[-1]
        res = max(res, data[loc]*sum(data[begin+1:i]))
    stack.append(i)  #  Index of records 
print(res)

This topic is very similar to Li Kou 84 topic ：
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/zhu-zhuang-tu-zhong-zui-da-de-ju-xing-by-leetcode-/

The following is the official bid answer , This implementation method , The monotonically increasing stack stores the sum of intervals , The implementation is ingenious ,debug To roughly understand

#  At present, this method has not been understood 

#  The main rules ： The smallest number in the interval is multiplied by the sum of all numbers in the interval 
#  Using monotone stack can solve this problem , First, enumerate all the elements to be the minimum number in the interval , The sum of all numbers in the interval is maintained through a stack 
#  The right boundary of the interval is the current enumerator , The left boundary of the interval is the stack top element （ The current number is less than the stack top element ）.
n = int(input())
arr = [int(x) for x in input().split()]
stack = []
arr.append(0)  #  Join the sentry , Avoid remaining elements in the stack , For the last element of the stack, it must be satisfied stack[-1] > arr[-1] At this point, the last element is calculated 

res = 0
presum = []  #  Used to store sections and 
tempsum = 0  #  Used to temporarily store the sum of out of stack data 

i = 0
while i < len(arr):
    #  If the stack is not empty and the top element of the stack is larger than the current element , The left boundary of the interval is found 
    if stack and stack[-1] > arr[i]:
        temp = stack.pop()  #  Out of the stack 
        tempsum += temp + presum.pop()  #  Calculating interval sum 
        res = max(res, tempsum*temp)  #  Determine whether it is the maximum interval and 
    else:
        #  If the stack is empty , Or the stack top element is smaller than the current element , First, store the recorded interval and in the stack 
        #  Then make the interval and return to 0, Indicates the end of the previous interval , Next is the new interval （ The stack top element is smaller than the current element ）
        presum.append(tempsum)
        tempsum = 0
        stack.append(arr[i])
        i += 1
print(res)