TheRealSamuel/LeetCodeProblem
0564
1{2 "id": 3211,3 "name": "find_maximum_non_decreasing_array_length",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/find-maximum-non-decreasing-array-length/",6 "date": "2023-11-11 00:00:00",7 "task_description": "You are given a **0-indexed** integer array `nums`. You can perform any number of operations, where each operation involves selecting a **subarray** of the array and replacing it with the **sum** of its elements. For example, if the given array is `[1,3,5,6]` and you select subarray `[3,5]` the array will convert to `[1,8,6]`. Return _the _**_maximum_**_ length of a _**_non-decreasing_**_ array that can be made after applying operations._ A **subarray** is a contiguous **non-empty** sequence of elements within an array. **Example 1:** ``` **Input:** nums = [5,2,2] **Output:** 1 **Explanation:** This array with length 3 is not non-decreasing. We have two ways to make the array length two. First, choosing subarray [2,2] converts the array to [5,4]. Second, choosing subarray [5,2] converts the array to [7,2]. In these two ways the array is not non-decreasing. And if we choose subarray [5,2,2] and replace it with [9] it becomes non-decreasing. So the answer is 1. ``` **Example 2:** ``` **Input:** nums = [1,2,3,4] **Output:** 4 **Explanation:** The array is non-decreasing. So the answer is 4. ``` **Example 3:** ``` **Input:** nums = [4,3,2,6] **Output:** 3 **Explanation:** Replacing [3,2] with [5] converts the given array to [4,5,6] that is non-decreasing. Because the given array is not non-decreasing, the maximum possible answer is 3. ``` **Constraints:** `1 <= nums.length <= 105` `1 <= nums[i] <= 105`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "nums = [5,2,2]",12 "output": "1 "13 },14 {15 "label": "Example 2",16 "input": "nums = [1,2,3,4]",17 "output": "4 "18 },19 {20 "label": "Example 3",21 "input": "nums = [4,3,2,6]",22 "output": "3 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 3723,29 18000,30 13200,31 89056,32 10473,33 63170,34 6481,35 27955,36 31404,37 44382,38 54026,39 39390,40 37678,41 851,42 9645,43 29152,44 8734,45 62113,46 1879,47 5004,48 2144,49 16266,50 4964,51 19579,52 39962,53 95509,54 55951,55 58204,56 32049,57 12497,58 29084,59 70250,60 23436,61 82404,62 99625,63 2377,64 48042,65 60131,66 82853,67 71752,68 25084,69 85307,70 21364,71 69993,72 98916,73 77763,74 54302,75 78642,76 41481,77 19624,78 50957,79 25128,80 39221,81 25716,82 13048,83 82337,84 83037,85 2810,86 8654,87 83150,88 11942,89 75053,90 25748,91 23728,92 35775,93 19369,94 69717,95 66139,96 84339,97 45769,98 4419,99 11784,100 18717,101 10911,102 46249,103 45542,104 59,105 69534,106 38013,107 85104,108 920,109 61360,110 26639,111 545,112 46131,113 12156,114 75301,115 61221,116 93471,117 42048,118 65130,119 49665,120 37054,121 30910,122 16255,123 60898,124 16410,125 64558,126 88061,127 41549,128 50025,129 91303,130 79893,131 99297,132 24086,133 66324,134 96880,135 5543,136 78684,137 87111,138 79237,139 47887,140 56499,141 45889,142 30929,143 48271,144 90999,145 85563,146 45996,147 79241,148 14950,149 73483,150 63328,151 13231,152 74401,153 73533,154 44180,155 183,156 21550,157 48002,158 58867,159 83078,160 76224,161 86444,162 51326,163 89633,164 33215,165 71297,166 91634,167 39340,168 519,169 77904,170 17793,171 86429,172 39707,173 81574,174 32232,175 367,176 38904,177 22653,178 2645,179 48264,180 17309,181 63218,182 97025,183 19881,184 5505,185 8481,186 13607,187 98747,188 36298,189 48770,190 79356,191 35247,192 85306,193 80452,194 73957,195 4114,196 48613,197 43640,198 99595,199 8614,200 19680,201 74035,202 43360,203 32443,204 21790,205 5444,206 3296,207 50073,208 6043,209 82678,210 50759,211 36361,212 51509,213 66645,214 19263,215 74674,216 2670,217 4191,218 62830,219 66492,220 84063,221 64577,222 7804,223 44724,224 50406,225 60981,226 54864,227 23335,228 59661,229 47567,230 37929,231 62611,232 73722,233 55309,234 69398,235 66870,236 21852,237 45170,238 64112,239 21988,240 20573,241 51996,242 36315,243 19746,244 30117,245 50864,246 67468,247 17134,248 18726,249 55618,250 58186,251 57391,252 4140,253 13890,254 33817,255 71046,256 61284,257 85671,258 43640,259 18360,260 49407,261 52892,262 13482,263 43505,264 84733,265 73195,266 95918,267 7101,268 50529,269 36829,270 41475,271 18818,272 84291,273 65330,274 24230,275 30584,276 50057,277 69028,278 65433,279 78835,280 31356,281 79301,282 56977,283 72541,284 81304,285 95183,286 75997,287 1217,288 33315,289 43733,290 25915,291 59702,292 81275,293 35252,294 29034,295 41110,296 24447,297 61571,298 83463,299 864,300 60960,301 11582,302 6824,303 9106,304 95792,305 76450,306 67771,307 56693,308 93863,309 67752,310 25852,311 80614,312 57540,313 63141,314 9273,315 35992,316 36743,317 73338,318 72988,319 84943,320 64862,321 15610,322 21665,323 77488,324 38470,325 34643,326 31439,327 68313,328 6486,329 96306,330 32381,331 56471,332 58775,333 56155,334 43100,335 83843,336 39189,337 91166,338 23186,339 65403,340 12225,341 68967,342 45500,343 48322,344 75444,345 60787,346 23048,347 85826,348 48331,349 80392,350 18726,351 69875,352 52042,353 50563,354 27298,355 90268,356 88524,357 56263,358 57172,359 83454,360 51652,361 19346,362 94527,363 78484,364 25514,365 24404,366 69263,367 83258,368 6279,369 69184,370 79249,371 32404,372 59968,373 70132,374 57364,375 73044,376 38147,377 49250,378 17107,379 53714,380 14265,381 47250,382 61923,383 25126,384 55732,385 79269,386 60577,387 15181,388 5143,389 8247,390 95895,391 32895,392 71343,393 74176,394 8594,395 29169,396 75851,397 17551,398 66283,399 8492,400 67781,401 56944,402 35438,403 64907,404 68307,405 35804,406 15871,407 58189,408 44297,409 90385,410 64059,411 36485,412 86997,413 14927,414 6756,415 53208,416 14717,417 94962,418 4696,419 46953,420 8285,421 49053,422 42191,423 41639,424 45882,425 5309,426 47376,427 356,428 99527,429 63286,430 50343,431 71395,432 73621,433 83991,434 50958,435 69454,436 35007,437 90674,438 97947,439 51022,440 22465,441 74779,442 55474,443 50914,444 18346,445 34978,446 73995,447 66681,448 1601,449 58860,450 31698,451 26680,452 22855,453 75373,454 91242,455 82217,456 10816,457 36354,458 18511,459 75371,460 10043,461 41189,462 40217,463 84229,464 5979,465 81855,466 83416,467 40845,468 4337,469 11682,470 56306,471 21129,472 42682,473 65541,474 88915,475 41684,476 19270,477 44511,478 43085,479 45116,480 64126,481 35716,482 36469,483 59037,484 35517,485 70840,486 46087,487 65680,488 53896,489 66228,490 63213,491 4513,492 29093,493 82857,494 41223,495 68300,496 86926,497 38802,498 40488,499 44167,500 15223,501 80032,502 98814,503 63357,504 40602,505 15862,506 83341,507 31008,508 23641,509 45484,510 56864,511 19079,512 47740,513 44087,514 93829,515 26677,516 94506,517 99991,518 67075,519 85097,520 68854,521 67058,522 10015,523 8331,524 51519,525 64895,526 13895,527 71005,528 75695,529 79877,530 4424,531 69620,532 87244,533 49529,534 23183,535 76810,536 80204,537 54842,538 18391,539 98161,540 33592,541 82758,542 32607,543 39645,544 72592,545 10680,546 67587,547 36549,548 28791,549 52049,550 31582,551 65333,552 89121,553 77111,554 6345,555 15321,556 6270,557 20916,558 75251,559 46694,560 82661,561 428,562 59723,563 74010,564 19324,565 24063,566 66019,567 62361,568 58482,569 41140,570 37504,571 35889,572 70725,573 78935,574 5494,575 89151,576 11627,577 54145,578 41535,579 34208,580 31516,581 26739,582 55008,583 46082,584 77333,585 60212,586 82020,587 50971,588 43686,589 48677,590 25859,591 42648,592 42679,593 41808,594 10065,595 54062,596 33111,597 61107,598 73890,599 85030,600 34112,601 75328,602 86320,603 55724,604 52650,605 57933,606 35219,607 25788,608 53569,609 33160,610 76022,611 48590,612 9105,613 20598,614 82791,615 21359,616 5293,617 89064,618 27146,619 37369,620 56601,621 90717,622 48454,623 45509,624 45118,625 44180,626 8803,627 36989,628 18120,629 39839,630 26035,631 36495,632 11978,633 54613,634 64464,635 60123,636 25970,637 42436,638 39881,639 46751,640 62446,641 31548,642 26019,643 62628,644 30697,645 89574,646 13711,647 4804,648 67210,649 85584,650 95728,651 21926,652 55226,653 28273,654 9994,655 35028,656 48103,657 22776,658 79298,659 52780,660 42624,661 95327,662 47524,663 59132,664 91062,665 38382,666 15901,667 83859,668 93658,669 77843,670 38106,671 34976,672 46980,673 3253,674 25908,675 93023,676 5145,677 33516,678 90206,679 89265,680 25224,681 30039,682 55384,683 81228,684 36332,685 3917,686 37787,687 91809,688 4739,689 86022,690 60511,691 41124,692 19201,693 12131,694 39202,695 75808,696 42613,697 90331,698 32750,699 28357,700 96818,701 26104,702 1914,703 57126,704 2264,705 52206,706 40775,707 30809,708 2731,709 33966,710 2821,711 11907,712 18985,713 54952,714 22520,715 70206,716 41501,717 4012,718 99756,719 64976,720 13722,721 85544,722 9045,723 60635,724 878,725 82552,726 59602,727 37609,728 98504,729 78361,730 6417,731 56530,732 80552,733 13957,734 84433,735 74407,736 75999,737 34227,738 19419,739 36740,740 2033,741 41780,742 61074,743 76163,744 77652,745 97362,746 66361,747 20217,748 55505,749 51030,750 1837,751 687,752 92833,753 44646,754 38875,755 49895,756 66026,757 17722,758 89605,759 35755,760 86850,761 43201,762 56961,763 8525,764 85814,765 79498,766 92036,767 21479,768 56961,769 55129,770 94876,771 54873,772 16861,773 76295,774 44605,775 82668,776 68515,777 27746,778 9297,779 81920,780 17131,781 35331,782 36161,783 5479,784 74774,785 13956,786 83266,787 85725,788 30420,789 17269,790 22229,791 96726,792 83306,793 47086,794 41885,795 68422,796 73614,797 74744,798 56719,799 81955,800 15446,801 12906,802 11591,803 29842,804 61386,805 78956,806 89235,807 22965,808 51636,809 7772,810 62414,811 25354,812 47619,813 5059,814 81653,815 17531,816 82663,817 73348,818 3330,819 98835,820 42598,821 67054,822 46639,823 70480,824 5992,825 43077,826 12802,827 43377,828 89821,829 88147,830 20709,831 5582,832 80142,833 20828,834 67595,835 12919,836 3232,837 75227,838 87551,839 29955,840 53772,841 21961,842 4511,843 16922,844 45488,845 79344,846 27550,847 27870,848 27166,849 14554,850 27931,851 75719,852 6055,853 43192,854 41019,855 49619,856 63529,857 11041,858 73353,859 92892,860 69118,861 27881,862 19677,863 51073,864 48702,865 50186,866 22883,867 55603,868 73277,869 7539,870 48661,871 50550,872 97920,873 47785,874 97749,875 32303,876 58269,877 54265,878 51997,879 42739,880 81078,881 10735,882 95242,883 95977,884 26259,885 66861,886 36819,887 86607,888 52522,889 39226,890 48265,891 75036,892 48052,893 66239,894 74643,895 15270,896 15698,897 70562,898 52219,899 91922,900 35481,901 38359,902 58430,903 37819,904 62059,905 75382,906 71772,907 38969,908 10303,909 97549,910 22075,911 307,912 78740,913 37494,914 47061,915 98531,916 18946,917 8045,918 30843,919 90716,920 51052,921 11481,922 29419,923 28755,924 75647,925 41894,926 37737,927 91777,928 42510,929 92243,930 2175,931 98918,932 57613,933 62590,934 65146,935 63269,936 99130,937 53764,938 57452,939 97965,940 6078,941 5058,942 12760,943 7129,944 88356,945 43991,946 42616,947 21304,948 38565,949 34578,950 30632,951 35063,952 10974,953 88994,954 69618,955 81185,956 63712,957 58627,958 19315,959 18422,960 16458,961 71903,962 62767,963 95879,964 55460,965 46933,966 31271,967 55053,968 86761,969 77101,970 94604,971 18916,972 56409,973 19901,974 41478,975 70178,976 84021,977 89088,978 22070,979 16244,980 968,981 87075,982 91057,983 99881,984 53471,985 29188,986 43029,987 55334,988 53339,989 15153,990 52915,991 5758,992 69572,993 94271,994 68483,995 92458,996 25170,997 42853,998 36678,999 4218,1000 19385,1001 56725,1002 56523,1003 1000,1004 83070,1005 43990,1006 76525,1007 52032,1008 24703,1009 3354,1010 65936,1011 18048,1012 3296,1013 22632,1014 57477,1015 22028,1016 88993,1017 9244,1018 47659,1019 75963,1020 11921,1021 32965,1022 36545,1023 76771,1024 77602,1025 14348,1026 32232,1027 90305,1028 58308,1029 47461,1030 26710,1031 45577,1032 12463,1033 64600,1034 74252,1035 74414,1036 6100,1037 14568,1038 12805,1039 86797,1040 33206,1041 77386,1042 48335,1043 64089,1044 23432,1045 2992,1046 11752,1047 6507,1048 45916,1049 78139,1050 43354,1051 63138,1052 37259,1053 39799,1054 81065,1055 59304,1056 88412,1057 87859,1058 11920,1059 34910,1060 785,1061 66575,1062 42884,1063 8194,1064 5219,1065 66857,1066 50965,1067 37901,1068 15192,1069 33292,1070 64942,1071 17038,1072 18623,1073 86084,1074 59221,1075 77654,1076 984,1077 54763,1078 83078,1079 71559,1080 1138,1081 89478,1082 95872,1083 10942,1084 59943,1085 81279,1086 6006,1087 46642,1088 49615,1089 49308,1090 20947,1091 64911,1092 93313,1093 40675,1094 2823,1095 92074,1096 75194,1097 28877,1098 18432,1099 53924,1100 92057,1101 48770,1102 2053,1103 62736,1104 2046,1105 76480,1106 59813,1107 210,1108 2398,1109 4828,1110 84299,1111 63929,1112 54301,1113 27466,1114 80811,1115 45526,1116 67159,1117 35274,1118 62508,1119 70106,1120 46533,1121 58959,1122 39316,1123 49226,1124 82655,1125 1361,1126 85695,1127 4441,1128 98773,1129 77645,1130 6256,1131 56199,1132 22617,1133 4047,1134 29410,1135 41895,1136 70687,1137 39710,1138 89154,1139 94199,1140 30900,1141 24876,1142 22067,1143 9208,1144 10339,1145 54734,1146 55659,1147 87046,1148 57723,1149 1120,1150 52342,1151 85490,1152 53656,1153 52445,1154 18544,1155 7127,1156 11429,1157 28053,1158 54163,1159 56538,1160 73811,1161 54603,1162 39228,1163 82131,1164 58466,1165 12573,1166 469,1167 81279,1168 60444,1169 53345,1170 18416,1171 41015,1172 61280,1173 83531,1174 18062,1175 27659,1176 83722,1177 96465,1178 76710,1179 51056,1180 27921,1181 73198,1182 16269,1183 52617,1184 29516,1185 10276,1186 87876,1187 15798,1188 34754,1189 4979,1190 80653,1191 95965,1192 69881,1193 15194,1194 90928,1195 76411,1196 43611,1197 94861,1198 47045,1199 41016,1200 71590,