1630 - largest rectangle
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 214
Solved: 102
- Description
- Given n positive integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height =[2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.
- Input
- The first line of the input file contains an integer T (T<=100) specifying the number of test cases.
Each test case begins with a line containing an integer N (1<=N<=100000),The following N-1 lines each contain a integer A[i](1<=A[i]<=10000).
- Output
- For each query, output a single line containing largest area.
- sample input
-
2 6 2 1 5 6 2 3 10 1 2 3 4 5 6 7 9 10 8
- sample output
-
10 30
- hint
- source
- The 8th(2013) ACM Programming Contest of HUST