CT63032

Quartermaster's Ledger of signals

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The valuer Quartermaster has been asked to prepare the expedition manifest. On the desk lies a long table of signals readings. 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: 1467 919182837 187490517 493363788 250000208 861459608 609829513 169954292 3121241 877282560 275527827 556857213 622102631 995905341 977157272 851283994 216124747 453363345 171995132 700882885 414963923 724127716 661297309 82156201 844920230 666831830 525657898 864449000 344766241 586508018 404465687 370023245 251405957 980158324 714443442 962186380 132134549 978934038 419103812 417966871 316249546 466863653 363450208 907761169 755891635 276606938 606406482 223713012 740957713 715864145 533160470 494665630 107512152 826731452 904822321 812260343 868348771 967032106 111830842 882042405 165674960 440290043 287284545 918767883 361387295 833733439 209451266 939067846 701142164 963909557 749856050 941639735 860807857 425998105 654740477 423967372 563007620 445334273 296527353 695166844 74697668…
Output: 12523078836

Example 2:

Input: 2725 747825507 932056909 953791242 361970467 32221205 278845042 703752544 2994946 151373080 543622633 737617221 960486497 494649778 419246110 4054816 226159399 26670049 315503901 477291247 180892940 961895216 625831936 653270732 423112073 105285459 689548274 130494557 55553609 665377358 73664704 110925867 766929406 644572322 956812588 472533775 133866296 212802853 309378240 831624540 768274515 831441993 354317655 626450557 843961277 757764852 652451410 719153993 425400749 823339580 42715489 701848341 262799609 357717631 522567751 25193030 447535461 269585513 746244390 192204344 249924386 369011400 897602578 965335061 489121601 870705067 656372650 427312337 312408092 789627085 80755330 21381850 87049639 893553353 611020105 656714901 316136998 918277548 677283397 337078671 246716500 59923930…
Output: 8123022039

Example 3:

Input: 2251 559992920 340583304 881169333 640750513 284993967 879595104 382283287 933408096 199903773 319456069 380592831 595022327 742885254 824676612 597901731 321570715 270000776 357448080 749443445 325067358 817592111 532525954 323084764 133708148 145396093 531273686 551298666 865444174 567410752 492240252 422807977 638425040 197547202 294205158 540046054 481753264 850424014 577993553 307487061 422019632 44319164 282926592 583889677 86068610 452460222 429436656 953992359 254737145 654287896 458896568 306594198 98401568 567666727 567261698 514673763 437060468 414507399 693806185 549564131 457474480 93994024 32783947 381913640 314387937 452158527 726955417 886573154 446951336 394933717 359907958 360953006 370903747 243444491 832882052 256366765 824610573 225969445 924301115 692397443 109469954 …
Output: 11466378070

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Quartermaster's Ledger of signals - MEDIUM Coding Problem | CodeTikki