CT57982

Jaya's Faded Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the gull cliffs of Screech Point opens only for a perfect tally of signals. Jaya means to find out. Task: Bars of heights h[i] stand side by side with width 1. Print the largest rectangle area that fits inside the histogram. Input format: First line: n. Second line: n heights. Output format: Print the maximum area (fits 64-bit). Constraints: 1 <= n <= 4000; 0 <= h[i] <= 10^9.

Example 1:

Input: 2619 758845328 754392653 372417396 576802278 588324185 774559184 504285211 750546172 878595978 237661014 91952469 482035348 347276933 315344357 888423124 425323758 391897536 428773138 353605209 54802408 390994363 776088490 77044028 691516997 289176864 812567463 952754434 961889730 714797682 581749404 559751390 949628936 770923480 505152969 349003359 821848342 809327698 925933524 611214242 628615822 91863186 816104578 672822213 612261699 466604426 771593392 636920718 869696733 95442875 243172339 497262944 126794413 173328868 229204058 873451683 30607074 734530492 645351722 29956468 533671073 806451671 336914913 190375675 594395995 126505407 18803592 544001671 244520524 989328903 732381475 151367257 50440530 512232577 903256799 815247163 302782687 852079101 161028154 75129786 150754114 10305…
Output: 11421542704

Example 2:

Input: 3995 836937547 251991922 290157932 601213658 388253456 457283871 923336839 520302046 333955816 245253706 564451189 584650173 33524370 989685883 88834482 666437593 201660613 134598705 255338256 840466662 338505524 135057881 862089634 131616890 589535348 149181634 998692048 381293712 106065036 837587280 5047619 235503246 841073909 768065840 857518737 478103693 96249538 136160251 224603914 259037481 814365858 256624563 977877566 716615171 198440105 355526185 277052673 345843006 344304367 208997173 95464146 247645233 789434488 311500092 401257922 600131769 203472458 549679767 431042559 695025134 189004571 657363783 700690868 985892166 869625238 554700759 908710898 648614242 425500155 145489793 665275044 809792027 524123374 698385634 200049177 587862984 845870902 750913761 740142664 962057274 7…
Output: 9237774168

Example 3:

Input: 3263 898414880 890245992 637635468 4197822 191331491 14327665 413388831 927641909 630477657 686684047 304798764 608799944 164087812 317254745 800148461 677584726 785723572 653817594 576493235 231620468 653575103 46404824 380307577 669745136 995998917 663420427 972941192 757730437 324455812 368897002 254179584 979124370 969659783 746174505 448014574 259306890 288022878 201291040 493705776 906454552 846638747 739801529 6811484 407362353 724268345 78489684 713424919 260457874 875331014 268561408 228430985 490520864 695374316 481201486 685314886 741461616 507984435 117870486 3461446 418263183 758490986 284218334 330620095 960204935 226067832 411463018 811500445 717690563 246083777 772733398 418836450 938905523 144853251 620380733 320129314 221628328 681288284 374567473 789977717 272287632 6819…
Output: 8922690748

Constraints:

1 <= n <= 4000; 0 <= h[i] <= 10^9.

Loading...
Test Cases:No test cases
No test cases available.
Jaya's Faded Ledger - MEDIUM Coding Problem | CodeTikki