CT57989

Lothar's Grand Facade Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the shale slopes of Greystone, someone must prepare the guildmaster's brief. This year the task falls to Lothar, armed only with the registers register. 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: 3002 21001451 455241111 713349339 666695330 546162746 694769883 920601759 104677229 870355773 526715356 977065190 33441631 660627036 502036051 769126821 472475881 823370376 391017454 214716355 464728193 650318295 52698091 694776601 598417194 370241644 430648877 206785967 134433823 418226126 84987282 520124081 658464996 541383125 525068940 555126950 670889970 208214216 808651618 564481855 388274770 499192597 464808938 68485891 214270486 43164975 981627234 159337263 710959662 249029043 982778893 449234363 889865225 803660310 164285905 442998532 238209136 121943811 151882683 847348170 453779897 61167448 563064567 119486064 867470171 80188161 563174936 185250671 965467782 257080761 273104989 444106385 31266186 253791254 84933878 849614234 760300421 999461025 703874094 714886885 625191099 73599…
Output: 8435324392

Example 2:

Input: 89 545009414 336577715 390566053 879962052 630204228 245804045 581970827 817470682 41609682 606859443 459094648 501151185 857849212 413047588 825863270 891202068 434750304 289034898 490293094 731488513 67867626 642081295 635566992 878767553 31295871 112934658 52485241 25471942 523027959 771414904 187385788 938127394 784537756 458169333 284672890 822735338 628957504 681443604 689591690 124939439 829694205 723608933 23138244 244614670 116589914 883007565 478699051 459862852 406265661 503404502 851695482 64933521 719965392 753670808 581491433 28944113 225183739 216862201 563073290 536284357 443205267 430346010 118499974 55438381 171954094 746915260 513146360 226260994 426330358 991948421 592465523 627709568 535750534 566786134 48005839 160091891 357546675 543523710 563549281 261803462 9813787…
Output: 3304380704

Example 3:

Input: 870 499150501 699252122 981053870 580914736 175720819 796929868 618206745 670254093 685176810 98174918 523935087 132516467 750480977 274232009 755829971 657756423 712442655 848902524 185241649 28974417 964038681 388802256 282897116 56080733 632459114 875143994 716743010 747162885 693630707 178023961 243959008 491483179 250086607 538224311 759027066 448379980 237008671 826834073 301666890 562958501 354156762 931898183 102969586 355557818 496808008 856572567 612267285 401101098 763589063 238882881 192987418 506316007 989552777 869721023 204430202 408809450 685256528 646378232 244921072 959288208 202416902 651389330 287601679 302992063 421027344 902462165 282306915 404672238 445923209 93560583 627219417 243851268 461002273 363156096 312536583 934212350 845606160 856677634 599240676 67356222 9…
Output: 9448851137

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Lothar's Grand Facade Ledger - MEDIUM Coding Problem | CodeTikki