알고리즘 어려움 코딩

히스토그램에서 가장 큰 직사각형

히스토그램에서 가장 큰 직사각형의 넓이를 구하세요

45분

150점

120개 테스트케이스

#3658

문제 설명

각 막대의 너비가 1인 히스토그램이 주어집니다.

히스토그램 내에서 만들 수 있는 가장 큰 직사각형의 넓이를 구하세요.

입력

첫째 줄에 막대 개수 N

둘째 줄에 N개의 막대 높이

출력

가장 큰 직사각형의 넓이

예제

입력:
6
2 1 5 6 2 3
출력: 10 (높이 5, 너비 2)

예제 테스트케이스

예제 1

입력

45
-456 -385 388 -343 475 764 -647 -874 -832 -996 994 651 519 531 692 959 29 535 70 406 874 411 -449 -806 -146 812 105 554 -192 161 -400 -633 748 474 659 -640 -996 -675 319 605 123 -27 939 792 995

출력

예제 2

입력

40
389 794 -412 114 240 -756 -275 274 -876 534 -107 -880 639 -972 -756 823 385 -56 -435 -569 -499 739 -203 602 -457 744 967 588 564 192 861 -706 375 917 -284 8 -524 -914 -20 -838

출력

예제 3

입력

2
-735 -983

출력

-1718

힌트

실행 버튼을 눌러 코드를 실행하세요.