Problem2286--柱状图中最大的矩形

2286: 柱状图中最大的矩形

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 6  Solved: 3
[Submit] [Status] [Web Board] [Creator:]

Description

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

Input

第一行一个整数n(n<=1e5)
第二行n个整数表示每根柱子的高度a[i](a[i]<=1e4)

Output

一个整数表示矩形的最大面积

Sample Input Copy

6
2 1 5 6 2 3

Sample Output Copy

10

Source/Category

  单调栈