Skip to content

12105: 【原2105】最大矩形

题目

题目描述

author: cherry_0804 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2105

Description

cs的妈妈买回来好多好多很长的纸条,这些纸条的宽度都是1,长度不同。淘气的cs把这些纸条剪了好多刀变得乱七八糟。cs看到这么多长长短短的纸条实在是无聊,于是把这些纸条全都摆了起来,变成下图:

最大矩形

摆成的纸条如左图,现在cs想知道其中最大的矩形是什么(如右图阴影部分),请你告诉她这其中最大的矩形面积是多少。

Input Format

第一行,一个整数N,表示有N个纸条。 第二行,N个用空格隔开的整数\(h_1,h_2, \cdots ,h_n\),表示每个纸条的长度

Output Format

一行,最大矩形的面积大小

Sample Input

7
2
1
4
5
1
3
3

Sample Output

8

Sample Input

4
1000
1000
1000
1000

Sample Output

4000

About Testdata

20%的数据,\(N \leq 100\)

40%的数据,\(N \leq 1000\)

100%的数据,\(N \leq 100,000, 0 < h_i < 1,000,000,000\)

Limits

Time limit: 1000ms, memory limit: 65536kb.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!