FPEvalDataset/LeetCodeProblem
0302
1{2 "id": 3313,3 "name": "maximum_strength_of_k_disjoint_subarrays",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/maximum-strength-of-k-disjoint-subarrays/",6 "date": "2024-03-03 00:00:00",7 "task_description": "You are given an array of integers `nums` with length `n`, and a positive **odd** integer `k`. Select exactly `k` disjoint subarrays `sub1, sub2, ..., subk` from `nums` such that the last element of `subi` appears before the first element of `sub{i+1}` for all `1 <= i <= k-1`. The goal is to maximize their combined strength. The strength of the selected subarrays is defined as: `strength = k * sum(sub1)- (k - 1) * sum(sub2) + (k - 2) * sum(sub3) - ... - 2 * sum(sub{k-1}) + sum(subk)` where `sum(subi)` is the sum of the elements in the `i`-th subarray. Return the **maximum** possible strength that can be obtained from selecting exactly `k` disjoint subarrays from `nums`. **Note** that the chosen subarrays **don't** need to cover the entire array. **Example 1:** **Input:** nums = [1,2,3,-1,2], k = 3 **Output:** 22 **Explanation:** The best possible way to select 3 subarrays is: nums[0..2], nums[3..3], and nums[4..4]. The strength is calculated as follows: `strength = 3 * (1 + 2 + 3) - 2 * (-1) + 2 = 22` **Example 2:** **Input:** nums = [12,-2,-2,-2,-2], k = 5 **Output:** 64 **Explanation:** The only possible way to select 5 disjoint subarrays is: nums[0..0], nums[1..1], nums[2..2], nums[3..3], and nums[4..4]. The strength is calculated as follows: `strength = 5 * 12 - 4 * (-2) + 3 * (-2) - 2 * (-2) + (-2) = 64` **Example 3:** **Input:** nums = [-1,-2,-3], k = 1 **Output:** -1 **Explanation:** The best possible way to select 1 subarray is: nums[0..0]. The strength is -1. **Constraints:** `1 <= n <= 104` `-109 <= nums[i] <= 109` `1 <= k <= n` `1 <= n * k <= 106` `k` is odd.",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [1,2,3,-1,2], k = 3",12 "output": "22 "13 },14 {15 "label": "Example 2",16 "input": "nums = [12,-2,-2,-2,-2], k = 5",17 "output": "64 "18 },19 {20 "label": "Example 3",21 "input": "nums = [-1,-2,-3], k = 1",22 "output": "-1 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 -73084530530 ],31 132 ],33 "output": -73084530534 },35 {36 "input": [37 [38 618326595,39 448389004,40 6556908841 ],42 343 ],44 "output": 102377086545 },46 {47 "input": [48 [49 204672809,50 -192913456,51 746662917,52 149975305,53 -66827866,54 -836128146,55 768165404,56 706674084,57 231331947,58 -296479966,59 -426136142,60 868629834,61 -870067878,62 -960752452,63 253326878,64 -539001173,65 805472369,66 -191685175,67 -436533967,68 917550163,69 864994024,70 479573356,71 -633929276,72 -303195757,73 -196063078,74 609559474,75 985343379,76 686022542,77 -610211663,78 20967351,79 82523708680 ],81 982 ],83 "output": 6781096305884 },85 {86 "input": [87 [88 -724506608,89 -368522704,90 793409335,91 365973363,92 -716414506,93 -978300938,94 -442697451,95 -657763402,96 522285831,97 385694299,98 43159125,99 136619060,100 527862830,101 -197920601,102 -613830251,103 -372504540,104 313494180,105 -443625367,106 -688966083,107 598966217,108 409908888,109 -589803840,110 -477730966,111 613241701,112 -390737414,113 -22022994,114 -547960724,115 -6229694,116 382085095,117 -376676611,118 -892084216,119 -347454643,120 -137395396,121 86262137,122 -819732419,123 -621173805,124 952996083,125 -9577676,126 -693761837,127 546636859,128 -514921345,129 526089743,130 -228794566,131 320901948,132 560908979,133 -546131898,134 293194647,135 -618884938,136 -152839247,137 77799811,138 -977521265,139 -615933919,140 -510266420,141 -553515438,142 103066643,143 824124712,144 -175912701,145 26234616,146 273758607,147 -760857837,148 639768230,149 390237609,150 -161945745,151 -834098873,152 950165490,153 902424192,154 -96048397,155 210673508,156 298747095,157 -190850202,158 -830915678,159 386839211,160 -93866394,161 -60727334,162 628676185,163 926839601,164 -751661617,165 108266933,166 636869260,167 77676798,168 466889329,169 899991294,170 -558332538,171 942588241,172 -68820724,173 575376213,174 -745714891,175 376586971,176 173608716,177 -795561806,178 -470931944,179 221966394,180 692779943,181 855872528,182 45936412,183 419520323,184 -833282041,185 368828830,186 127639841,187 -446640806,188 655541660,189 -818747788,190 572439097,191 252039748,192 -62418661,193 905621817,194 222024057,195 618970986,196 -187455764,197 -745190831,198 -866347292,199 691723984,200 601396702,201 337165280,202 967835592,203 -85782078,204 -831351802,205 -307220378,206 27116151,207 169953096,208 -878728640,209 72261237,210 -846557342,211 -284780353,212 -694476555,213 427126481,214 256558323,215 -912167677,216 21839037,217 219126317,218 -924765548,219 -391882268,220 -322716989,221 -763059384,222 683408965,223 662496195,224 -589480926,225 -66571053,226 -800875023,227 929903857,228 -769205895,229 -396273248,230 750851984,231 950343556,232 -291857638,233 -99467074,234 296341725,235 -252821837,236 180996229,237 494542741,238 114755227,239 -737786396,240 -831112412,241 -876313321,242 -632700504,243 -938615012,244 -386115461,245 -834255671,246 550713924,247 -756041179,248 -347535309,249 -180289124,250 201814063,251 -709248243,252 488558688,253 216509385,254 -783202006,255 827163333,256 -770868647,257 -198701934,258 -530727906,259 935796185,260 -315565797,261 702912524,262 122836502,263 -131263762,264 -43505615,265 377283393,266 279249384,267 -321836342,268 -22762785,269 -685043685,270 -838130219,271 -25798416,272 577750607,273 -376975328,274 177934448,275 64174390,276 -928451714,277 -205252998,278 -759766489,279 -175409706,280 -621028807,281 -199491497,282 672294342,283 667640724,284 628963570,285 -742618375,286 618413187,287 207516702,288 80564834,289 558601196,290 -798132697,291 -729483116,292 709369195,293 765622471,294 946228285,295 -322032359,296 806173187,297 945662189,298 -809858506,299 475229823,300 936826912,301 -248231890,302 366194971,303 675272554,304 -688298448,305 459833945,306 606409709,307 552578350,308 -956641647,309 -128460244,310 292792580,311 716188216,312 -244393565,313 459245158,314 674014553,315 457138561,316 672300488,317 880554712,318 -773431324,319 753202013,320 -332039927,321 -665108035,322 -808379981,323 799796429,324 127179490,325 -847164768,326 -465171737,327 666989138,328 -137069939,329 -975916385,330 269408849,331 244150920,332 -629423219,333 579637062,334 -131161196,335 -109967098,336 13145658,337 -956115617,338 513396207,339 687030380,340 581108362,341 37309222,342 -771126480,343 943874852,344 659807774,345 455036292,346 537909190,347 688055182,348 169293452,349 32683115,350 -588342064,351 -299238113,352 904468235,353 19841302,354 -290693667,355 -801867360,356 -784363816,357 297864519,358 -576906855,359 -644699515,360 674384420,361 -734838082,362 131752681,363 639200259,364 -595041232,365 220225275,366 480943338,367 -233971733,368 64775674,369 -799636893,370 667344788,371 -489229398,372 -714690737,373 165269406,374 36090265,375 200506802,376 370684401,377 -729240530,378 -321455373,379 749164358,380 147317708,381 -45484633,382 756105509,383 -309405369,384 -866165895,385 -764135782,386 -467986855,387 843446423,388 544894598,389 440952306,390 -721029381,391 -347314287,392 146466626,393 -213277724,394 48661078,395 -256700690,396 -295545218,397 -368443333,398 -960297631,399 685322425,400 -419265340,401 674400369,402 807190632,403 -788880336,404 -949652757,405 -70889371,406 -63045362,407 -495429196,408 -728284831,409 -48622672,410 -325283189,411 556788333,412 -339326400,413 -906480869,414 146001265,415 145859680,416 -63543056,417 -949798455,418 -933702190,419 -98145166,420 -122669522,421 859716728,422 526185013,423 57326791,424 -366158794,425 -284859191,426 653383558,427 -454815580,428 585087469,429 468570840,430 662691097,431 -805020558,432 119465737,433 -201855025,434 -554716255,435 -109544839,436 -500112376,437 151409639,438 -5860482,439 395428100,440 767053718,441 -824255046,442 781529091,443 -486565230,444 -207354578,445 -575970333,446 -359320097,447 -130911152,448 -919224015,449 416346385,450 -274299570,451 121587610,452 -890041177,453 862190880,454 -545074406,455 498801383,456 108875076,457 -460379777,458 854101508,459 83060477,460 -113571091,461 702219228,462 -139499895,463 575036269,464 -124656053,465 346825688,466 -14685070,467 672958297,468 723541615,469 415384993,470 815193610,471 -779971260,472 801687246,473 -339057297,474 59698619,475 -314149198,476 254749186,477 514487735,478 -454507891,479 485900861,480 189693101,481 -591239066,482 873450486,483 696699210,484 -501473782,485 -844470944,486 -558692545,487 58275250,488 847142997,489 -234832256,490 -391734934,491 -428092799,492 255714441,493 -652489709,494 996783835,495 -76219624,496 398696657,497 -595467651,498 -647423339,499 -830362406,500 656161148,501 481870591,502 71608651,503 -562061669,504 137254175,505 73957639,506 785812114,507 833074521,508 -90781240,509 -324765509,510 -264831022,511 -867039031,512 699900589,513 248799697,514 973474916,515 -961650061,516 349758904,517 116555420,518 -543873614,519 239991017,520 -324077673,521 -787715563,522 -989911589,523 134285892,524 977208209,525 -144858212,526 151745467,527 592699225,528 247631899,529 586172065,530 406473978,531 -85473779,532 141733938,533 354946140,534 -285686961,535 -124052566,536 522349960,537 238997640,538 400524706,539 898623187,540 -447979244,541 559660017,542 115330821,543 -585866241,544 302910357,545 168929955,546 -447856700,547 548957759,548 628523285,549 -446158596,550 -828934031,551 -228581478,552 -956508477,553 -129610583,554 -172221541,555 -787500879,556 787237207,557 353964176,558 471886932,559 -100362320,560 464392798,561 -312216601,562 546633594,563 -2536271,564 881955588,565 456495291,566 389232677,567 -614736282,568 105740548,569 605760261,570 875874276,571 966054230,572 -707525323,573 814334030,574 538840504,575 -550657260,576 754150393,577 604584442,578 -805304228,579 386056475,580 695148631,581 387757770,582 977242842,583 308591535,584 -525626807,585 -276982035,586 -351077683,587 893992171,588 518052530,589 -148099168,590 536689701,591 -473734894,592 -971639491,593 -332835875,594 -159439631,595 -161238573,596 -631027741,597 543135641,598 -155508211,599 62185369,600 399860062,601 172488849,602 907233102,603 822741284,604 -250930032,605 -380401023,606 282284457,607 301245089,608 155373056,609 -98995806,610 88751028,611 -388895328,612 -193321042,613 -972277550,614 -211053301,615 433849927,616 302835157,617 549730851,618 916871854,619 -260655577,620 -295969765,621 446232889,622 535093109,623 -2429439,624 -885567597,625 -331496331,626 847521825,627 253518032,628 613278343,629 -183517324,630 408771375,631 923527365,632 224809005,633 813248572,634 390904752,635 854252149,636 -563629638,637 -949065298,638 205062877,639 -705205874,640 609972044,641 -425503531,642 452079383,643 775187020,644 -773218255,645 -482669106,646 -813323686,647 -843101543,648 -295786167,649 582721632,650 -237662552,651 820003105,652 446347766,653 -406405978,654 399983643,655 -973794638,656 438459428,657 -722406256,658 681479375,659 871904627,660 -118951501,661 93615585,662 887154841,663 -108298886,664 -361361580,665 -897891844,666 367175167,667 628002862,668 779198178,669 555756939,670 460469137,671 -979144076,672 101219901,673 -1365207,674 275102663,675 148805106,676 -406815320,677 122404241,678 -244329364,679 403900641,680 -619695595,681 56945772,682 375348983,683 -16217328,684 -597850442,685 121119610,686 738995879,687 359735399,688 686785129,689 -539860680,690 707618490,691 -701492942,692 856255627,693 -366255625,694 66167209,695 789392780,696 75789726,697 -910873090,698 -638674737,699 615560793,700 9070509,701 -200262243,702 -733684509,703 -246200850,704 327396725,705 -494822970,706 338366543,707 238787663,708 -976316330,709 758516494,710 90056866,711 457821774,712 -259117164,713 21593514,714 620646566,715 -342838912,716 -659702997,717 117341583,718 -235478376,719 6558530,720 -98250809,721 -864670214,722 -408958302,723 920266440,724 696801043,725 -366758038,726 379072019,727 -751473338,728 -605960955,729 288371912,730 304858707,731 237833452,732 -436735286,733 141642565,734 -976293173,735 549907724,736 -74760933,737 249821024,738 267479457,739 733302816,740 -244889315,741 445374190,742 -550511356,743 101831357,744 -865162030,745 723261130,746 192740954,747 -45853215,748 814264302,749 -937052415,750 465257465,751 991096115,752 915086643,753 83417225,754 325964681,755 -312378164,756 -482109757,757 946721856,758 -445245422,759 318393395,760 382308974,761 -622307358,762 -273567413,763 491208298,764 432724869,765 -624739713,766 955334559,767 111577629,768 861726100,769 600805473,770 -969033181,771 -916573921,772 -412003583,773 937934918,774 -907205057,775 362095172,776 -905009383,777 -80358991,778 -838908159,779 -708962222,780 888978271,781 991343440,782 896555079,783 905425213,784 -357218389,785 322757313,786 -885781456,787 -601871173,788 -399475733,789 -221369846,790 698539032,791 -469422742,792 467683063,793 635424136,794 503590684,795 -799667948,796 300789445,797 777044595,798 -509605694,799 596968303,800 231653751,801 303435108,802 968744352,803 714199467,804 -713454443,805 -709778495,806 822025927,807 -282567824,808 695417539,809 334222187,810 -324932382,811 943038170,812 -940645946,813 -316078282,814 -5835673,815 -789382949,816 -630290372,817 -483545668,818 327098386,819 164204308,820 -221473440,821 -952956436,822 410363683,823 55122808,824 -192295025,825 -28373715,826 -78033618,827 -466643223,828 -490117813,829 -222941611,830 254651919,831 348932472,832 782387280,833 891728735,834 -537521804,835 -166952561,836 410004050,837 -257446273,838 432331890,839 -868803518,840 969919846,841 349137503,842 583202617,843 -93986160,844 -234088420,845 -650750276,846 603816005,847 -2562163,848 551105232,849 212988974,850 -315282885,851 -910905321,852 878274045,853 -734618758,854 64390725,855 -520850489,856 416029272,857 92897485,858 458289990,859 -787948836,860 -203876010,861 855992822,862 618397091,863 -572364647,864 -980180361,865 -257753066,866 -534657268,867 -576040235,868 823088200,869 637507003,870 -718067826,871 159107438,872 -702851629,873 -246793508,874 -274064428,875 -282721955,876 580384869,877 -861798298,878 598703119,879 -136610178,880 629418296,881 -344809121,882 556604430,883 -207265973,884 370307341,885 886847062,886 132342162,887 -899304712,888 563409149,889 -678870773,890 409442761,891 648404439,892 -97974863,893 -222994084,894 802974954,895 -921217225,896 854123232,897 -764903705,898 220562021,899 -186098621,900 335611610,901 -132997375,902 867286181,903 -460194548,904 -889401768,905 -444106473,906 832346361,907 280514492,908 220988030,909 33293506,910 350770756,911 144205822,912 -315948687,913 -519348748,914 482641424,915 -992795363,916 -674627583,917 732976293,918 -702687505,919 -601520516,920 714380962,921 -603980743,922 -311194016,923 335614226,924 794124022,925 -206975695,926 633898368,927 -22776877,928 438148768,929 -156313843,930 -166268359,931 452539103,932 -769050905,933 -309427759,934 680221078,935 -673682208,936 -154434893,937 -409845450,938 935950005,939 220085091,940 482328916,941 662598865,942 374321101,943 637695696,944 69518861,945 538433678,946 68324084,947 -633751651,948 411124318,949 -388390940,950 86522952,951 -129581928,952 217055012,953 -144016389,954 -137339004,955 370502716,956 510701070,957 -817381275,958 921713166,959 748268435,960 892508860,961 88388169,962 131764196,963 148593276,964 -84897229,965 -787755027,966 781619417,967 782560296,968 491417830,969 42582571,970 -941881788,971 -88689891,972 -826805562,973 160116420,974 -214685980,975 -33554928,976 -519184773,977 268263311,978 -493716341,979 582234583,980 -336168445,981 515968326,982 -987544020,983 -388246755,984 -94315954,985 -877609556,986 -576823513,987 -669186668,988 -117792514,989 -954841094,990 278226268,991 647872309,992 599143582,993 -452496583,994 -912248946,995 105818815,996 595243015,997 -746203283,998 468373404,999 -340006574,1000 -163566408,1001 200671881,1002 -619839680,1003 -519533439,1004 467657840,1005 366088942,1006 618472246,1007 -729565379,1008 -575703348,1009 -867399895,1010 -698265106,1011 683148827,1012 848959978,1013 -230503983,1014 67919272,1015 -558592666,1016 -162326038,1017 374694836,1018 -548846594,1019 -660269220,1020 -712467003,1021 -391460163,1022 -720969580,1023 -42675321,1024 251144760,1025 -383959283,1026 418741524,1027 -870429165,1028 -458424871,1029 510227988,1030 -831679763,1031 37607902,1032 -5759054561033 ],1034 51035 ],1036 "output": 2193175427081037 },1038 {1039 "input": [1040 [1041 -421685080,1042 -261478808,1043 100743722,1044 329434066,1045 752703763,1046 -584740343,1047 861588017,1048 -946947201,1049 -522065784,1050 -193921171,1051 687966813,1052 80505729,1053 692445260,1054 -850075637,1055 -873909786,1056 -582329366,1057 -97164697,1058 435568890,1059 -647749779,1060 875293946,1061 53756327,1062 931676860,1063 584551468,1064 -402396412,1065 527672625,1066 -37961055,1067 -511635830,1068 674628245,1069 -773063118,1070 -999177108,1071 57602361,1072 980944588,1073 774004664,1074 -437595904,1075 -24696482,1076 664889018,1077 755591917,1078 663504456,1079 955715731,1080 -588574815,1081 649358370,1082 258519674,1083 324066112,1084 -418513756,1085 -131459719,1086 -589088530,1087 678936876,1088 76761182,1089 460154130,1090 903865357,1091 848760778,1092 -348564783,1093 431499997,1094 -654814157,1095 -606699953,1096 -72443913,1097 -677708665,1098 -436855385,1099 353679382,1100 854774586,1101 255462945,1102 942430309,1103 645201714,1104 -466494430,1105 241215654,1106 47153257,1107 -764304712,1108 -458347066,1109 -61746289,1110 594525123,1111 -977316044,1112 -210596582,1113 550732684,1114 630486605,1115 -322816696,1116 630155433,1117 -496842044,1118 975209920,1119 -918413972,1120 453312033,1121 417184840,1122 -927558584,1123 -226109493,1124 -96140640,1125 769312535,1126 -725983625,1127 473679164,1128 663685240,1129 -791334364,1130 592539667,1131 -904060766,1132 957780464,1133 561345318,1134 -157947161,1135 393562210,1136 -99539080,1137 -76254813,1138 300937740,1139 -576722120,1140 428317343,1141 15059549,1142 -198685443,1143 910401382,1144 -544040956,1145 159133919,1146 902072519,1147 506446564,1148 281992883,1149 -524274272,1150 -991109959,1151 869176099,1152 -356402633,1153 -468895194,1154 -917883176,1155 918491173,1156 100630457,1157 716530238,1158 946842219,1159 407561661,1160 -815895840,1161 659817669,1162 470608978,1163 854947041164 ],1165 91166 ],1167 "output": 1683356582901168 },1169 {1170 "input": [1171 [1172 -532636915,1173 -584089138,1174 -80526250,1175 -545458736,1176 -588980563,1177 -310081192,1178 -206819106,1179 -538882116,1180 -303997277,1181 -260422604,1182 -740905504,1183 -752885745,1184 -11732066,1185 -459804665,1186 -318066004,1187 -198288109,1188 -303102386,1189 -318993751,1190 -96307574,1191 -944348369,1192 -34927672,1193 -505861812,1194 -472340248,1195 -455660523,1196 -653618566,1197 -225074116,1198 -890400969,1199 -346184879,1200 -1983166,