FPEvalDataset/LeetCodeProblem
0305
1{2 "id": 3113,3 "name": "beautiful_towers_ii",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/beautiful-towers-ii/",6 "date": "2023-09-17 00:00:00",7 "task_description": "You are given a **0-indexed** array `maxHeights` of `n` integers. You are tasked with building `n` towers in the coordinate line. The `ith` tower is built at coordinate `i` and has a height of `heights[i]`. A configuration of towers is **beautiful** if the following conditions hold: `1 <= heights[i] <= maxHeights[i]` `heights` is a **mountain** array. Array `heights` is a **mountain** if there exists an index `i` such that: For all `0 < j <= i`, `heights[j - 1] <= heights[j]` For all `i <= k < n - 1`, `heights[k + 1] <= heights[k]` Return _the **maximum possible sum of heights** of a beautiful configuration of towers_. **Example 1:** ``` **Input:** maxHeights = [5,3,4,1,1] **Output:** 13 **Explanation:** One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since: - 1 <= heights[i] <= maxHeights[i] - heights is a mountain of peak i = 0. It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13. ``` **Example 2:** ``` **Input:** maxHeights = [6,5,3,9,2,7] **Output:** 22 **Explanation:** One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since: - 1 <= heights[i] <= maxHeights[i] - heights is a mountain of peak i = 3. It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22. ``` **Example 3:** ``` **Input:** maxHeights = [3,2,5,5,2,3] **Output:** 18 **Explanation:** One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since: - 1 <= heights[i] <= maxHeights[i] - heights is a mountain of peak i = 2. Note that, for this configuration, i = 3 can also be considered a peak. It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18. ``` **Constraints:** `1 <= n == maxHeights.length <= 105` `1 <= maxHeights[i] <= 109`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "maxHeights = [5,3,4,1,1]",12 "output": "13 "13 },14 {15 "label": "Example 2",16 "input": "maxHeights = [6,5,3,9,2,7]",17 "output": "22 "18 },19 {20 "label": "Example 3",21 "input": "maxHeights = [3,2,5,5,2,3]",22 "output": "18 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 818285741,29 607617451,30 735866601,31 598930260,32 899460492,33 2660828,34 681419595,35 382919309,36 242080287,37 388065900,38 323211807,39 956267513,40 677700970,41 520928405,42 346173939,43 837978437,44 248064270,45 111712576,46 527845439,47 427290128,48 112497440,49 415269802,50 44851045,51 945931176,52 224293580,53 493570801,54 181595623,55 279427297,56 974284345,57 361915861,58 557846220,59 573073192,60 662548241,61 866043187,62 746404240,63 263643381,64 109799700,65 209982734,66 476993083,67 657520904,68 958025636,69 904357542,70 950624906,71 908851112,72 79870897,73 104665668,74 363153334,75 306148615,76 266642131,77 121194818,78 878980274,79 973322489,80 138806049,81 272019913,82 523850767,83 967211476,84 634755319,85 637438226,86 723483748,87 157587138,88 665103423,89 865519438,90 94581768,91 435107176,92 636916072,93 167269086,94 272742032,95 463917477,96 118057027,97 535059788,98 201629118,99 641491635,100 155302095,101 198437539,102 511947040,103 607028373,104 811541635,105 894867645,106 259954822,107 966056654,108 119182131,109 662784155,110 851639150,111 592763532,112 100030581,113 854698198,114 329443338,115 445815365,116 655180386,117 937211466,118 242658889,119 592633677,120 592662893,121 949170481,122 85657624,123 79848815,124 326624548,125 547118741,126 793091007,127 596966086,128 94233384,129 181005445,130 287296993,131 785303945,132 204447656,133 745353782,134 629955908,135 377879923,136 850321373,137 405005978,138 65889481,139 834204314,140 37214593,141 214977592,142 644659150,143 380004441,144 977488082,145 518118483,146 660711440,147 148463404,148 369410241,149 644896135,150 148355047,151 901170625,152 165948519,153 240323580,154 849191302,155 557105925,156 834520743,157 157033990,158 422933718,159 645603024,160 209523303,161 719973716,162 440788456,163 937908805,164 53474534,165 684155412,166 704411589,167 542755485,168 928230898,169 913298078,170 198457961,171 666245321,172 407912282,173 451654776,174 664627312,175 40582907,176 312494819,177 12579068,178 829353972,179 586547233,180 955969463,181 607630394,182 508010831,183 327844070,184 582887257,185 170638808,186 560335121,187 345463174,188 987530442,189 782233281,190 696349587,191 168374901,192 961728630,193 25328059,194 374842222,195 352487356,196 780315232,197 275284806,198 122291764,199 767539587,200 732157586,201 382435456,202 704168101,203 780483660,204 229695933,205 321162423,206 779113225,207 798012386,208 877675756,209 987897290,210 175575260,211 562294849,212 44166952,213 632084182,214 678649732,215 234739651,216 197245996,217 761993109,218 688957253,219 167356532,220 683231812,221 925903417,222 185316958,223 523752144,224 178721251,225 208404659,226 40855463,227 689126495,228 14240478,229 255737858,230 125641504,231 319923316,232 116241288,233 926353025,234 785300381,235 309799258,236 897261539,237 870721862,238 225635387,239 368443666,240 789181232,241 500776889,242 78319445,243 960904272,244 579772405,245 181725458,246 530797663,247 286924086,248 340160400,249 806411863,250 710737303,251 850342112,252 990469666,253 187989778,254 382699140,255 300845149,256 39456894,257 616375109,258 220954643,259 882717246,260 298080424,261 118436280,262 146118841,263 109429501,264 183048289,265 699645745,266 409499620,267 17810928,268 994554230,269 559507045,270 935986221,271 778005675,272 507414131,273 777038875,274 898395185,275 916552872,276 415597506,277 473065353,278 17766052,279 977110332,280 933441145,281 193290912,282 345140127,283 325335905,284 352137489,285 739643019,286 659636061,287 389225125,288 615546853,289 809478238,290 541555385,291 657944990,292 118695083,293 643492131,294 43747575,295 641790050,296 971782093,297 940842955,298 458039747,299 578734807,300 999882336,301 347461585,302 119240039,303 867307124,304 281077534,305 923497878,306 815901687,307 404932971,308 235938385,309 675646730,310 211876241,311 794029018,312 531165925,313 617456307,314 793294668,315 233815442,316 132261273,317 740982310,318 545151594,319 818267500,320 255238234,321 116349409,322 365602299,323 529272855,324 295656640,325 818983064,326 570937063,327 674774536,328 756611101,329 83291278,330 445653154,331 626336727,332 39395959,333 207510832,334 32722431,335 370025066,336 804112601,337 244328999,338 482455067,339 305654045,340 321235687,341 972820992,342 984771924,343 407168498,344 180034472,345 722613892,346 463603177,347 253255505,348 288236511,349 683584626,350 463042520,351 103730694,352 752342297,353 448505193,354 84701398,355 714745644,356 465982242,357 371700035,358 491539912,359 538841467,360 532185805,361 5857418,362 514645400,363 611714681,364 917502632,365 266810775,366 879654134,367 385277231,368 801177075,369 899673273,370 92087864,371 232008529,372 409044815,373 668252626,374 942132104,375 256859730,376 454176281,377 728302448,378 504949251,379 933749785,380 184727706,381 90350857,382 124392318,383 97651977,384 741166063,385 37725690,386 672347585,387 966841759,388 655427105,389 803853370,390 675363812,391 808578654,392 586577170,393 697364493,394 536591866,395 49252440,396 75538348,397 608488237,398 142257226,399 60975130,400 25089456,401 738498604,402 798331369,403 163086769,404 256365818,405 912492231,406 114534203,407 563021898,408 177253795,409 140245086,410 594263508,411 941623771,412 126135895,413 286731100,414 781480892,415 567739041,416 566720589,417 117395182,418 945124101,419 541682571,420 643911743,421 668843343,422 366890860,423 937923947,424 764799391,425 715398366,426 415658731,427 274535770,428 946303587,429 934448716,430 285120245,431 836631664,432 691942539,433 544503382,434 521785065,435 199660182,436 896401838,437 382076825,438 561134443,439 294293308,440 720951252,441 846419753,442 336572847,443 577660177,444 535667710,445 839480971,446 586445751,447 286059592,448 589335821,449 611791698,450 134415046,451 811227335,452 444536556,453 369366022,454 527420703,455 869717540,456 724959778,457 307220500,458 865647810,459 442769036,460 591074765,461 211335941,462 326666917,463 242088998,464 238514317,465 135677067,466 808206003,467 823241494,468 690397578,469 626819911,470 316117698,471 913880392,472 164985796,473 200467038,474 494050653,475 634735269,476 810681799,477 587792252,478 453522160,479 19360573,480 415169301,481 287081789,482 653913531,483 882090598,484 742406929,485 99017970,486 910894378,487 268916866,488 18778318,489 604310258,490 722528223,491 368805184,492 565393595,493 903653241,494 301432076,495 206475824,496 120341438,497 508880608,498 546926898,499 970500581,500 558366528,501 907319133,502 298403143,503 142126806,504 850425026,505 514046704,506 313108779,507 958655952,508 763473614,509 987628052,510 851304196,511 154311849,512 291810476,513 50426067,514 41822754,515 913731223,516 71143323,517 452995392,518 292015984,519 556857617,520 578728245,521 367551653,522 140312230,523 914520364,524 487812909,525 271136670,526 592862363,527 470594633,528 824577386,529 36081162,530 592567532,531 697569237,532 39928593,533 47274565,534 161486644,535 727762883,536 249421046,537 195589141,538 891245040,539 10564094,540 390536873,541 664847367,542 529719371,543 880637791,544 911546922,545 521510821,546 952949537,547 321420034,548 836111409,549 64201216,550 78124366,551 760361768,552 922337298,553 52759395,554 290821743,555 698858509,556 475564411,557 684017960,558 289638687,559 590747153,560 69229689,561 344812196,562 638149203,563 240487424,564 670054789,565 386230096,566 302493956,567 698838504,568 582960002,569 291716460,570 657027659,571 864862708,572 302038284,573 754028165,574 833382324,575 227870974,576 225549381,577 753823735,578 866979415,579 595683125,580 244433858,581 303665622,582 189376465,583 103901424,584 862978559,585 932901345,586 983805959,587 480187274,588 25331251,589 394062355,590 58742237,591 386110991,592 239565385,593 947206784,594 119564986,595 831013241,596 823603780,597 999574284,598 168368314,599 684760903,600 586807915,601 186003296,602 703175001,603 408042092,604 812348443,605 845336811,606 381845498,607 624489401,608 33071163,609 495728556,610 58106403,611 995184393,612 818096376,613 611337779,614 441046459,615 383702986,616 757360814,617 718912408,618 308333702,619 252570459,620 511741073,621 287802242,622 993393155,623 587324954,624 343664264,625 54936688,626 348619492,627 133478554,628 57679542,629 53769677,630 427259754,631 628421642,632 794914495,633 758805560,634 924152921,635 530485449,636 827918654,637 742946072,638 68310797,639 812371247,640 997716686,641 581463961,642 737785882,643 111399389,644 465811351,645 516982248,646 256478102,647 716659871,648 442373798,649 698188623,650 408057111,651 371306963,652 737021750,653 12571567,654 754290117,655 229631970,656 189562796,657 234820903,658 938115903,659 773105103,660 927446287,661 9004857,662 352153826,663 256350046,664 899091063,665 590570127,666 694540051,667 853613697,668 75427772,669 815670340,670 19824500,671 514695311,672 261467485,673 753146042,674 2030669,675 48045839,676 992096977,677 166581919,678 551287644,679 547360598,680 315550425,681 530039859,682 393939668,683 829907712,684 133850866,685 98084155,686 344448336,687 615549730,688 904486111,689 68322400,690 662843516,691 605957295,692 801757582,693 154611220,694 751287343,695 950675309,696 854967850,697 820071587,698 696138003,699 891129372,700 954487701,701 42427660,702 921543442,703 415739636,704 544945560,705 706760743,706 898026320,707 421706986,708 196551686,709 26905585,710 426220760,711 914278907,712 221669576,713 279687636,714 275354962,715 487168506,716 562877750,717 783979641,718 729250116,719 225050465,720 66705359,721 718895800,722 932724706,723 192531322,724 626850226,725 369180830,726 333815328,727 525758297,728 171900181,729 508046645,730 580175323,731 920277477,732 484251241,733 9873865,734 637384125,735 916096052,736 945859344,737 911892105,738 171367939,739 700708931,740 5035655,741 961352435,742 835453732,743 935500679,744 572599198,745 376416457,746 596153980,747 541837254,748 664975644,749 215312042,750 26954454,751 204858794,752 690749952,753 650964661,754 574934502,755 513815065,756 615818870,757 101498065,758 978225753,759 782493852,760 991944045,761 744622249,762 637024104,763 155498625,764 482236785,765 329820762,766 164937813,767 722372380,768 151252146,769 210651915,770 990522022,771 75607690,772 33331395,773 404128855,774 706781170,775 434297331,776 237353765,777 442876651,778 75251525,779 779482079,780 311846624,781 462966438,782 866057258,783 61539612,784 990724707,785 657117562,786 217142170,787 124869775,788 167036236,789 774834765,790 787816356,791 374431844,792 311758537,793 728927695,794 956660164,795 605432547,796 943819221,797 233224324,798 437369678,799 372750509,800 549061444,801 541456660,802 194395927,803 914337453,804 889454899,805 546646890,806 787801422,807 187746968,808 998653694,809 321099318,810 181743812,811 139072236,812 841145502,813 998607886,814 229357511,815 77308579,816 461010359,817 603112746,818 256144379,819 318132200,820 902052597,821 592188100,822 197940058,823 98629595,824 799250550,825 887534754,826 481675556,827 86222571,828 374550560,829 624476711,830 510015002,831 563987316,832 70746028,833 276044279,834 135105612,835 420227862,836 876569015,837 2929484,838 149617884,839 921401154,840 572918286,841 170358524,842 407575865,843 8694173,844 186499882,845 903547396,846 739838330,847 271239089,848 322817149,849 709432917,850 149768022,851 333595389,852 853587889,853 470190938,854 955685960,855 596542683,856 11943527,857 879983045,858 158396036,859 604282307,860 883232233,861 882103134,862 493748408,863 204494251,864 131869085,865 243419563,866 8703746,867 74581046,868 710919322,869 910933506,870 211164406,871 709942500,872 582898064,873 773567264,874 141210109,875 237407726,876 476104664,877 516787663,878 643059084,879 860826703,880 12540768,881 191749628,882 875635647,883 251540838,884 705355330,885 787238282,886 398823117,887 36158915,888 896385401,889 917233104,890 385441392,891 796717926,892 618480047,893 944665785,894 199677004,895 961849547,896 866567001,897 843820619,898 105267133,899 857256345,900 452314055,901 290344731,902 225274164,903 918954960,904 96087249,905 585434030,906 410574294,907 213311506,908 797094200,909 446385966,910 501473968,911 76558341,912 685620458,913 836415182,914 742918287,915 854078945,916 760994163,917 919523496,918 37022084,919 751887541,920 43722543,921 768267403,922 826000724,923 16600496,924 824030079,925 386449231,926 533585587,927 974056069,928 551521175,929 469501892,930 353559188,931 740214918,932 232043905,933 913933737,934 107757997,935 848551706,936 475765906,937 412309742,938 618304868,939 615376678,940 12450734,941 312641845,942 42033434,943 3977605,944 861026323,945 955985906,946 619118545,947 410525618,948 329570844,949 139456350,950 162398781,951 389245436,952 779895993,953 964905620,954 413795591,955 337992524,956 939015417,957 464588192,958 599606523,959 638307375,960 118136539,961 9648610,962 796217692,963 357433074,964 759602599,965 245775720,966 191402315,967 563885957,968 928673210,969 327586147,970 249348117,971 964193296,972 237358259,973 66876822,974 589977688,975 667113369,976 535178841,977 230245446,978 120005522,979 448687087,980 762452718,981 515720963,982 960210458,983 524425149,984 88354451,985 631631778,986 347191951,987 27315742,988 963428308,989 57991573,990 563296378,991 344599439,992 977203236,993 156111024,994 439311201,995 163936456,996 141465658,997 382340903,998 682148428,999 568707795,1000 251878990,1001 317527540,1002 418652477,1003 621330942,1004 201214759,1005 636849160,1006 398334421,1007 912251603,1008 679093721,1009 194961507,1010 130140571,1011 842128783,1012 552571490,1013 154882961,1014 703842235,1015 772936409,1016 348412861,1017 900618523,1018 711678437,1019 522271883,1020 28417823,1021 978979995,1022 953205193,1023 616054967,1024 347525193,1025 87570743,1026 11486902,1027 265742027,1028 87353409,1029 800770388,1030 346561743,1031 486215803,1032 297329084,1033 240179807,1034 853693595,1035 146039509,1036 655858718,1037 825821563,1038 84234852,1039 331550026,1040 458606741,1041 23080591,1042 483272264,1043 787756943,1044 492007900,1045 225348352,1046 354545908,1047 444237170,1048 463520547,1049 834170372,1050 564034332,1051 517863887,1052 305063433,1053 837922579,1054 298509811,1055 518611928,1056 482559927,1057 230467443,1058 798821253,1059 896005844,1060 778047020,1061 671129133,1062 246877528,1063 249684471,1064 293658851,1065 536369212,1066 300848832,1067 396869809,1068 822247257,1069 637468899,1070 391111157,1071 623060679,1072 717650601,1073 603136302,1074 829429353,1075 578149349,1076 241454785,1077 183578768,1078 796778631,1079 342649761,1080 96471797,1081 668618119,1082 681160350,1083 379340752,1084 141637448,1085 865253925,1086 542296601,1087 261612469,1088 619310601,1089 607483236,1090 964771833,1091 160755567,1092 918079092,1093 418508898,1094 49323582,1095 653245024,1096 450045781,1097 761220881,1098 456725269,1099 264804217,1100 381747914,1101 291767516,1102 166099618,1103 984173706,1104 466222893,1105 348405934,1106 492321562,1107 646978282,1108 448894085,1109 427822739,1110 360426442,1111 305721704,1112 601852409,1113 189578262,1114 777312219,1115 351192821,1116 234251098,1117 654838804,1118 308852805,1119 605152113,1120 26184819,1121 411341019,1122 457400281,1123 603017120,1124 869601879,1125 621055329,1126 524988922,1127 950749934,1128 388449265,1129 283692002,1130 497768195,1131 919335296,1132 267503136,1133 695945057,1134 128223711,1135 412252912,1136 396466794,1137 954886833,1138 957411620,1139 290170407,1140 558519158,1141 704215151,1142 471736695,1143 248198036,1144 856401120,1145 871947292,1146 220393297,1147 604661722,1148 592856874,1149 806850177,1150 926550730,1151 510443340,1152 887838160,1153 372493346,1154 729822456,1155 780492249,1156 890718584,1157 922668090,1158 140271009,1159 438718696,1160 968150118,1161 793889956,1162 140685388,1163 561140189,1164 398615714,1165 911856350,1166 666070066,1167 371652617,1168 704946005,1169 780696100,1170 290923713,1171 258407290,1172 70829899,1173 126381436,1174 442949702,1175 187759821,1176 385930221,1177 93665288,1178 348901713,1179 197268338,1180 32189220,1181 458817403,1182 395422129,1183 974294651,1184 99918381,1185 201888728,1186 396760262,1187 672852084,1188 769930876,1189 302956976,1190 898074700,1191 511877730,1192 416807335,1193 879224787,1194 532337794,1195 905283130,1196 379092377,1197 274941366,1198 736586847,1199 382982543,1200 459785439,