TheRealSamuel/LeetCodeProblem
0572
1{2 "id": 2655,3 "name": "rearrange_array_to_maximize_prefix_score",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/rearrange-array-to-maximize-prefix-score/",6 "date": "1677974400000",7 "task_description": "You are given a **0-indexed** integer array `nums`. You can rearrange the elements of `nums` to **any order** (including the given order). Let `prefix` be the array containing the prefix sums of `nums` after rearranging it. In other words, `prefix[i]` is the sum of the elements from `0` to `i` in `nums` after rearranging it. The **score** of `nums` is the number of positive integers in the array `prefix`. Return _the maximum score you can achieve_. **Example 1:** ``` **Input:** nums = [2,-1,0,1,-3,3,-3] **Output:** 6 **Explanation:** We can rearrange the array into nums = [2,3,1,-1,-3,0,-3]. prefix = [2,5,6,5,2,2,-1], so the score is 6. It can be shown that 6 is the maximum score we can obtain. ``` **Example 2:** ``` **Input:** nums = [-2,-3,0] **Output:** 0 **Explanation:** Any rearrangement of the array will result in a score of 0. ``` **Constraints:** `1 <= nums.length <= 105` `-106 <= nums[i] <= 106`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [2,-1,0,1,-3,3,-3]",12 "output": "6 "13 },14 {15 "label": "Example 2",16 "input": "nums = [-2,-3,0]",17 "output": "0 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 999641,24 999457,25 999389,26 998943,27 998846,28 998406,29 998366,30 998099,31 997672,32 997609,33 997586,34 997413,35 997348,36 997243,37 997006,38 996425,39 996383,40 995546,41 995487,42 995363,43 995207,44 995004,45 994964,46 994893,47 994881,48 994857,49 994665,50 994200,51 994004,52 994003,53 993886,54 993850,55 993613,56 993265,57 993130,58 993064,59 993029,60 992957,61 992875,62 992746,63 992558,64 992297,65 992035,66 991423,67 991159,68 990974,69 990929,70 990738,71 990415,72 990110,73 990078,74 989898,75 989694,76 989549,77 989489,78 989378,79 988301,80 988052,81 987589,82 987444,83 987302,84 987292,85 987281,86 987231,87 987210,88 987077,89 987046,90 987000,91 986950,92 986792,93 986726,94 986697,95 986642,96 986631,97 986517,98 986350,99 986265,100 985889,101 985666,102 985653,103 985627,104 985267,105 984473,106 984190,107 984100,108 984041,109 984032,110 984029,111 983949,112 983616,113 983539,114 982967,115 982596,116 982413,117 982384,118 982235,119 982061,120 981841,121 981394,122 981307,123 981128,124 981026,125 981014,126 980910,127 980863,128 980795,129 980633,130 980388,131 980122,132 980028,133 979829,134 979813,135 979571,136 979295,137 979097,138 978976,139 978955,140 978486,141 978257,142 978111,143 977373,144 977172,145 976720,146 976354,147 976177,148 975790,149 975585,150 975540,151 975513,152 974981,153 974714,154 974604,155 974540,156 974215,157 974150,158 973918,159 973804,160 973727,161 973569,162 973472,163 973353,164 973285,165 973107,166 972956,167 972951,168 972878,169 972705,170 972311,171 972250,172 972135,173 972099,174 972050,175 971977,176 971800,177 971657,178 971414,179 971104,180 970924,181 970701,182 970678,183 970406,184 970337,185 970256,186 970109,187 970089,188 970048,189 969951,190 969941,191 969895,192 969883,193 969802,194 969539,195 969329,196 968979,197 968934,198 968855,199 968729,200 968658,201 967810,202 967715,203 967320,204 967293,205 967239,206 966981,207 966636,208 965910,209 965854,210 965850,211 965525,212 965359,213 965068,214 965053,215 964726,216 964315,217 964268,218 963796,219 963787,220 963780,221 963369,222 963290,223 962786,224 962670,225 962449,226 962392,227 962300,228 962125,229 962109,230 962087,231 962076,232 961464,233 961448,234 961335,235 961331,236 961237,237 960631,238 960566,239 960153,240 960038,241 959918,242 959916,243 959742,244 959725,245 959664,246 959064,247 959045,248 958773,249 958656,250 958175,251 957685,252 957590,253 957057,254 957016,255 956457,256 956089,257 955826,258 955382,259 955279,260 955052,261 954918,262 954871,263 954801,264 954441,265 954129,266 953978,267 953973,268 953477,269 953367,270 953314,271 953262,272 953188,273 952986,274 952743,275 952503,276 952459,277 952328,278 952224,279 951787,280 951501,281 951376,282 951307,283 951072,284 951017,285 950819,286 950799,287 950690,288 950384,289 950092,290 949798,291 949207,292 949150,293 949032,294 948936,295 948841,296 948557,297 948309,298 948242,299 948112,300 948108,301 947550,302 947030,303 947021,304 946915,305 946857,306 946729,307 946464,308 946393,309 946384,310 945963,311 945918,312 945612,313 945156,314 945011,315 944607,316 944423,317 943900,318 943876,319 943772,320 943653,321 943625,322 943100,323 942990,324 942833,325 942263,326 942257,327 941538,328 941460,329 941429,330 941417,331 941390,332 941313,333 940661,334 940650,335 940618,336 940496,337 939982,338 939960,339 939858,340 939673,341 938916,342 938682,343 938658,344 938177,345 938119,346 937755,347 937502,348 937158,349 937074,350 936993,351 936976,352 936969,353 936375,354 936159,355 936033,356 935766,357 935700,358 935497,359 935193,360 935133,361 935106,362 935068,363 934816,364 934742,365 934654,366 934590,367 934405,368 934059,369 933461,370 933208,371 932966,372 932863,373 932681,374 932658,375 932474,376 932456,377 932256,378 932117,379 931969,380 931931,381 931369,382 931236,383 931056,384 930949,385 930934,386 930883,387 930820,388 930805,389 930715,390 930413,391 930216,392 929992,393 929907,394 929336,395 929301,396 928982,397 928918,398 928442,399 928247,400 928184,401 928066,402 927834,403 927579,404 927579,405 927305,406 927280,407 926851,408 926805,409 926719,410 926684,411 926543,412 926464,413 926340,414 926240,415 926239,416 925627,417 925603,418 925535,419 925132,420 924891,421 924722,422 924594,423 924525,424 924488,425 924450,426 924438,427 924313,428 924204,429 924130,430 924009,431 923915,432 923730,433 923354,434 923193,435 923141,436 923022,437 922997,438 922826,439 922645,440 922638,441 922486,442 922145,443 921947,444 921765,445 921561,446 921545,447 920991,448 920842,449 920818,450 920614,451 920160,452 920041,453 919841,454 919690,455 919690,456 919675,457 919616,458 919604,459 919491,460 919456,461 919307,462 919276,463 919084,464 918853,465 918698,466 918459,467 918364,468 918142,469 918119,470 918098,471 917838,472 917768,473 917533,474 917446,475 917438,476 917286,477 917285,478 916938,479 916790,480 916512,481 916479,482 916294,483 915799,484 915502,485 915252,486 914963,487 914537,488 914178,489 914134,490 914009,491 913750,492 913643,493 913450,494 913446,495 913376,496 913290,497 912992,498 912817,499 912459,500 912402,501 912333,502 912162,503 912098,504 911944,505 911944,506 911872,507 911814,508 911788,509 911478,510 911368,511 911309,512 911263,513 911146,514 911122,515 910991,516 910981,517 910696,518 910431,519 910396,520 910325,521 910300,522 910296,523 910259,524 910186,525 909947,526 909778,527 909743,528 909312,529 908960,530 908809,531 908755,532 908632,533 908308,534 908035,535 907959,536 907895,537 907882,538 907808,539 907466,540 907452,541 907402,542 907389,543 907168,544 906757,545 906660,546 905634,547 905407,548 905006,549 904953,550 904613,551 904501,552 904129,553 904081,554 903771,555 903559,556 903474,557 903418,558 902930,559 902442,560 902243,561 902235,562 902044,563 901939,564 901325,565 901201,566 901126,567 901090,568 900778,569 900597,570 900418,571 900417,572 900056,573 899865,574 899018,575 898901,576 898895,577 898025,578 897989,579 897886,580 897402,581 897295,582 897128,583 896710,584 896614,585 896589,586 896495,587 896351,588 896075,589 896032,590 895965,591 895392,592 895303,593 894940,594 894913,595 894846,596 894688,597 894597,598 894497,599 894373,600 894138,601 893930,602 893612,603 893347,604 893239,605 893216,606 893176,607 893167,608 892947,609 892670,610 892662,611 892535,612 892424,613 892207,614 892131,615 891634,616 891411,617 891184,618 891072,619 890825,620 890463,621 890340,622 890201,623 889719,624 889629,625 889392,626 889361,627 889189,628 888843,629 888822,630 888353,631 887354,632 886969,633 886906,634 886829,635 886745,636 886389,637 886276,638 886172,639 885590,640 885541,641 885343,642 885087,643 884907,644 884757,645 884582,646 884236,647 884055,648 883863,649 883850,650 883575,651 883551,652 883286,653 882590,654 881925,655 881736,656 881643,657 881084,658 880819,659 880370,660 880051,661 879990,662 879989,663 879970,664 879880,665 879009,666 878692,667 878476,668 878193,669 877835,670 877424,671 877397,672 877147,673 877064,674 876891,675 876855,676 876791,677 876667,678 876241,679 876222,680 876174,681 876112,682 875974,683 875907,684 875891,685 875731,686 875481,687 875154,688 875093,689 874816,690 874792,691 874373,692 874087,693 873937,694 873814,695 873358,696 872937,697 872774,698 872170,699 871963,700 871696,701 871446,702 871433,703 871180,704 871140,705 871136,706 870878,707 870768,708 870624,709 870608,710 870562,711 870535,712 870526,713 870465,714 870158,715 869781,716 869675,717 869673,718 869660,719 869508,720 869322,721 869271,722 868754,723 868526,724 868287,725 868176,726 868004,727 867914,728 867909,729 867780,730 867607,731 867571,732 867242,733 867183,734 866977,735 866928,736 866759,737 866708,738 866592,739 866180,740 866103,741 865830,742 865628,743 865435,744 865323,745 865181,746 864887,747 864362,748 864249,749 864175,750 863650,751 863649,752 863415,753 863298,754 863024,755 862896,756 862836,757 862730,758 862686,759 862439,760 862132,761 862069,762 861845,763 861818,764 861550,765 861239,766 861136,767 861019,768 860824,769 860528,770 860423,771 860300,772 860172,773 859915,774 859763,775 859737,776 859454,777 859216,778 858777,779 858629,780 857984,781 857832,782 857768,783 857548,784 857376,785 857265,786 857211,787 856707,788 856646,789 856518,790 856512,791 856066,792 855858,793 855836,794 855691,795 855616,796 855540,797 855266,798 855220,799 855039,800 854839,801 854765,802 854677,803 854508,804 854430,805 854273,806 853976,807 853521,808 853233,809 852966,810 852798,811 852701,812 852570,813 852561,814 852234,815 852204,816 852029,817 851888,818 851561,819 851444,820 851127,821 851097,822 850799,823 850259,824 850184,825 850074,826 849486,827 849397,828 849371,829 849285,830 848989,831 848897,832 848866,833 848813,834 848550,835 848450,836 848115,837 848075,838 847531,839 847219,840 847102,841 847032,842 847002,843 846925,844 846900,845 846814,846 846779,847 846713,848 846516,849 846429,850 846228,851 846206,852 845323,853 845011,854 844646,855 844570,856 844517,857 844407,858 844039,859 843782,860 843615,861 843609,862 843530,863 842981,864 842941,865 842832,866 842474,867 842358,868 842020,869 841730,870 841258,871 841119,872 841114,873 841030,874 841019,875 840877,876 840618,877 840146,878 840120,879 839445,880 839275,881 839239,882 839222,883 838992,884 838935,885 838887,886 838725,887 838374,888 838326,889 838221,890 838132,891 838127,892 838105,893 838084,894 837996,895 837904,896 837816,897 837588,898 837495,899 837493,900 837354,901 837171,902 837058,903 836713,904 836638,905 836201,906 836185,907 836134,908 836072,909 836012,910 835943,911 835911,912 835910,913 835838,914 835694,915 835553,916 835518,917 835373,918 834944,919 834828,920 834826,921 834492,922 834400,923 834360,924 834218,925 834187,926 834153,927 834110,928 833660,929 833619,930 833228,931 833150,932 833109,933 833082,934 832982,935 832920,936 832804,937 832797,938 832632,939 832532,940 832318,941 832106,942 832067,943 831855,944 831510,945 831061,946 830804,947 830730,948 830698,949 830377,950 830350,951 830002,952 829900,953 829190,954 829127,955 829033,956 829018,957 829013,958 828642,959 828361,960 828104,961 827688,962 827518,963 827301,964 827059,965 827057,966 827034,967 826245,968 826089,969 825839,970 825656,971 825536,972 825483,973 825097,974 825056,975 824710,976 824164,977 823740,978 823590,979 823521,980 823515,981 823495,982 823493,983 823146,984 822880,985 822850,986 822820,987 822638,988 822463,989 821853,990 821732,991 821397,992 821191,993 821169,994 821152,995 821011,996 820884,997 820812,998 820347,999 820153,1000 819943,1001 819840,1002 819775,1003 819607,1004 819033,1005 818795,1006 818729,1007 817563,1008 817255,1009 816980,1010 816857,1011 816502,1012 816438,1013 816360,1014 816039,1015 815858,1016 815823,1017 815542,1018 815508,1019 815363,1020 815237,1021 814805,1022 814501,1023 814355,1024 814324,1025 814307,1026 813915,1027 813110,1028 812768,1029 812736,1030 812586,1031 812449,1032 811829,1033 811521,1034 811442,1035 811230,1036 811171,1037 811144,1038 810767,1039 810573,1040 810308,1041 810153,1042 809892,1043 809587,1044 809458,1045 809135,1046 809076,1047 809031,1048 809022,1049 808640,1050 808520,1051 808199,1052 808069,1053 807895,1054 807591,1055 807534,1056 807406,1057 807259,1058 807232,1059 807211,1060 806752,1061 806706,1062 806638,1063 806612,1064 806597,1065 806230,1066 806214,1067 806089,1068 805993,1069 805968,1070 805427,1071 805252,1072 805180,1073 805027,1074 805017,1075 804997,1076 804968,1077 804881,1078 804634,1079 803957,1080 803766,1081 803675,1082 803449,1083 803349,1084 803197,1085 803157,1086 802878,1087 802458,1088 802173,1089 802129,1090 801974,1091 801930,1092 801748,1093 801698,1094 801653,1095 801499,1096 801404,1097 801168,1098 801044,1099 800884,1100 800797,1101 800749,1102 800675,1103 800582,1104 800365,1105 800254,1106 800028,1107 799991,1108 799946,1109 799943,1110 799691,1111 799493,1112 798985,1113 798834,1114 798374,1115 797671,1116 797457,1117 796990,1118 796979,1119 796742,1120 796349,1121 796010,1122 795512,1123 795286,1124 795190,1125 795111,1126 794933,1127 794100,1128 793970,1129 793585,1130 793316,1131 793293,1132 793156,1133 792584,1134 792452,1135 792445,1136 791979,1137 791965,1138 791746,1139 791635,1140 791344,1141 791013,1142 790835,1143 790220,1144 789977,1145 789968,1146 788984,1147 788892,1148 788719,1149 788561,1150 788339,1151 788226,1152 788039,1153 787903,1154 787595,1155 787417,1156 787219,1157 787166,1158 787031,1159 786986,1160 786957,1161 786846,1162 786524,1163 786470,1164 786469,1165 786392,1166 786317,1167 786179,1168 786163,1169 785965,1170 785949,1171 785911,1172 785867,1173 785666,1174 785159,1175 784948,1176 784835,1177 784835,1178 784785,1179 784742,1180 784531,1181 784427,1182 784408,1183 783881,1184 783848,1185 783784,1186 783704,1187 783686,1188 783664,1189 783620,1190 783512,1191 783492,1192 783434,1193 783028,1194 783021,1195 782780,1196 782771,1197 782677,1198 782439,1199 782353,1200 782300,