Longest Increasing Subsequence

Dynamic ProgrammingGenome Rearrangements

Descrizione

Data una permutazione, una sottosequenza è una collezione dei suoi elementi presi nell'ordine in cui appaiono. È crescente se gli elementi aumentano, decrescente se diminuiscono. Il problema chiede la più lunga sottosequenza crescente e la più lunga sottosequenza decrescente di una data permutazione.

Given

Un intero positivo n ≤ 10000, seguito da una permutazione π di lunghezza n.

Return

Una più lunga sottosequenza crescente di π, seguita da una più lunga sottosequenza decrescente di π.

Sample Dataset

5
5 1 4 2 3

Sample Output

1 2 3
5 4 2

La mia esecuzione

08/24/2026 11:24:47

Input · dataset.txt

9531
8324 3657 6898 7096 1783 2358 3305 2451 7151 6810 1732 6880 4572 4571 1565 7980 4811 4199 3338 5274 1617 4378 8999 987 4087 7342 750 4501 7656 1319 2468 496 5456 632 2768 5554 5198 5998 3449 3868 9417 7119 7461 148 3747 6300 2745 3836 6046 727 2234 1014 573 1450 4403 8041 288 6577 4413 4257 6945 6094 6062 7370 947 7727 1452 1149 2126 5602 1652 6453 8330 83 6647 747 7195 3911 4844 6415 5759 7760 44 4019 8971 7437 4058 6037 2281 7039 7865 2285 6917 5534 6413 7231 3818 1902 3497 4964 9247 2372 2480 2713 9226 4990 3369 9349 3909 4708 408 2428 2471 2246 4454 3529 2156 2717 5304 5712 5983 8751 1922 722 2790 431 4238 3176 9510 2332 858 8297 5825 5463 6128 8884 7441 7243 5417 2743 2739 5757 2594 5309 9051 7810 5331 3310 2393 5856 1230 1796 4535 2427 2884 6151 3601 6372 8460 4711 5545 626 695 6721 7817 2308 8342 5846 5770 5732 7685 8859 2680 6544 9125 7194 3049 7425 569 7655 3102 2155 6164 1977 3057 1767 3527 2095 743 1514 3943 6618 9003 6844 1520 4005 792 3137 7690 6036 733 453 6187 1264 6344 76 549 8224 2942 7496 480 3145 4329 1511 1596 1778 2975 3645 4558 8803 1989 7051 5933 1876 1935 8938 8725 1424 1973 7892 7091 4720 7193 4455 8289 7897 2298 7633 962 4225 9292 6484 6229 6334 3185 5875 1869 588 7230 9429 3474 5703 2351 2924 2571 4491 1112 1539 4377 1369 3900 9312 3090 1509 4363 1801 2319 7380 4861 8082 2365 4843 472 3748 380 2755 2665 4985 2482 7548 6356 4004 9471 6331 4036 7203 2796 419 2989 4912 1681 260 7847 6854 1775 8192 7887 5653 2214 6724 4894 2149 1623 7993 8418 9340 4865 7016 5735 8404 7214 3479 6761 311 9034 449 259 3808 1854 154 3110 9177 4918 6703 4386 4592 2384 6156 1605 3551 176 3575 8588 5733 9067 7795 152 2299 6920 3283 5117 3481 4633 9272 8924 9257 8821 9076 4504 5027 2060 2160 9253 3972 5860 9142 8052 6524 9325 7958 3605 9363 910 9332 1220 7984 7828 7808 1510 2094 913 3084 1784 314 5130 5775 4251 4277 4362 1086 316 4566 8308 3533 9385 3296 4396 1003 4125 9085 1167 3949 3104 5621 7310 5496 4727 261 9197 4485 3002 2092 6723 4743 2997 7305 3614 3012 2090 8296 4408 180 4676 8577 3436 5360 8732 996 1540 2644 6135 8017 9099 9333 3434 7990 9060 7288 5026 7937 8567 1033 3640 7612 3954 382 1749 6690 617 2912 1804 8674 1221 5341 6913 3643 9209 9039 6100 4911 8716 354 7185 6213 7736 3089 8400 1551 2820 3736 6043 3412 5094 8793 2402 649 6756 2065 2712 9174 5 7483 361 961 31 3274 4314 1701 3260 5980 4232 2807 5739 4242 1878 8977 8963 810 5750 2654 4321 3930 317 4398 6395 9178 713 1795 2108 6781 5478 9077 1865 3292 1912 2682 1179 356 7295 7744 768 2741 441 7715 8385 6420 6016 7781 247 9469 8887 8658 5411 5802 161 6083 2251 1375 3327 2074 7404 2008 1200 8802 8433 4310 9336 3617 8188 352 8829 7362 1327 1422 1025 6063 5693 8922 446 7603 8965 1995 8699 2570 4002 1812 2431 6904 64 7679 3844 5886 4679 1924 1451 6157 5560 9044 6001 8535 3574 7002 6900 4529 7232 4229 6827 423 5491 7789 2413 5676 3169 1398 2811 1814 970 4904 7549 4874 4264 1343 7957 6986 1324 7198 5698 8691 7688 8830 543 9531 6175 3933 6027 3284 4046 8980 1075 5308 642 753 6117 2580 7382 1434 6758 5661 8058 1430 7818 1262 5854 7891 2957 2907 6256 615 7704 1833 8956 9518 6856 729 5692 6548 8718 7409 6039 9015 8562 4555 7199 8771 2519 1668 1860 1023 5460 4267 7777 8018 4372 5529 3703 6353 9155 4300 9365 2086 3496 4476 4756 8271 1453 7577 1959 272 4942 1558 9527 438 5189 8858 432 845 8346 5300 8849 1225 3100 5929 1101 9186 1145 3590 8947 3631 3843 8303 7954 4620 4193 1773 6707 8536 5249 589 6737 5617 5981 6211 2378 6385 8653 244 4612 4210 8374 1682 8707 6482 6149 5209 9117 8377 5269 1555 4733 4043 4420 4301 8635 684 6817 1141 6028 5208 3150 8452 198 6189 8179 2727 3817 1432 4868 6974 4269 3767 1114 2987 7029 8415 2253 3458 5425 8091 4466 2866 1651 547 6845 1064 6821 4715 8060 4062 2762 9151 1325 643 6352 9074 4434 1542 6258 3803 1638 3521 6015 233 7135 4696 2486 74 7995 3 4746 1900 4839 1917 2093 7845 5326 9043 7251 6335 5725 732 4489 7394 4074 6714 2503 6319 8483 8432 725 8158 3282 4256 5867 2509 5831 6836 8935 1290 1441 7722 5391 2779 4412 3707 2951 5957 8241 3468 8005 3478 366 9492 726 560 8539 1807 94 904 7745 2408 4626 8655 4176 9500 7532 5441 3024 8822 1990 5543 8355 7554 3587 6591 4181 8472 299 1055 3637 1093 1390 7361 5768 2198 1993 454 222 6718 8212 1037 2802 2458 3440 3827 3714 9211 319 1181 5774 7732 5634 2350 5938 7360 983 4085 2873 3528 5748 7072 1355 7238 1384 129 4688 2335 3820 5000 9033 6155 3414 5214 1916 5316 8112 3409 6443 8270 1541 9187 1224 923 8826 6178 5173 3437 8955 6462 5267 1419 9418 7692 8309 2355 8013 1386 1507 8273 5904 5616 4486 5656 4614 8285 239 3055 8155 1818 6346 1081 7676 8492 1852 7831 205 8619 2295 5205 5029 8045 3917 3289 4659 194 4849 3851 2449 6261 4041 470 4607 8078 9392 6154 4887 2140 7036 3639 7546 2288 5526 3428 7229 4870 481 6545 8253 4666 3114 7976 2020 4900 2889 8959 2076 7209 7062 8997 534 3648 7966 7099 456 3931 2908 5358 3255 3549 590 5185 4078 816 4892 3582 4589 6379 579 1068 5659 3160 4060 8269 2500 6481 6745 6572 1580 1650 6293 3035 957 9497 8478 18 9274 2208 3477 6222 9443 2946 633 3408 5227 4891 4761 1601 6740 1027 2262 3047 1353 275 3929 5658 2033 8944 7794 6058 4582 7798 5503 3059 4950 8299 6081 6343 2283 7104 9037 934 9054 8198 2958 4735 428 2196 2815 5089 7148 6893 2784 237 284 8247 5594 7584 8688 8607 2352 5641 7213 5339 5273 1090 5470 9267 2639 1042 7102 5445 8474 4966 1413 3498 4721 7765 1864 2289 1187 2881 7885 312 5648 9456 4214 4263 7872 4227 5241 2991 3789 8109 1387 3386 7657 7156 4776 2897 1815 801 952 5410 9273 5167 8435 8023 7451 4575 65 8238 2598 4459 3774 2368 2995 7613 334 2670 508 8064 7500 6226 3419 5009 8995 5035 6931 1238 3913 8762 6106 2789 9290 5787 7494 7889 3995 3834 5877 7708 6967 5612 7371 8628 4563 1382 79 283 5558 4319 4934 2337 6605 8437 6646 5146 8406 9045 3592 5809 6078 965 2168 2758 4026 6031 5773 3899 212 2765 8640 3511 4946 9105 8788 1702 8638 853 3040 2833 8835 6567 6358 8226 6417 4524 929 2087 4203 7738 3191 2723 7073 3969 1296 7748 8113 2278 3422 4907 6654 1856 6152 500 1227 1665 4353 1473 5415 8337 3689 3940 6400 4332 6255 1926 5671 7641 4247 8930 6936 5521 8768 3599 6207 2371 969 7762 3782 8002 9278 3269 350 8428 8636 4718 5754 7943 3421 2800 1728 7862 7392 9350 163 513 6955 5738 3027 3275 7537 838 1974 6012 3041 5796 2611 3948 6895 7418 2695 1207 7628 8403 1140 2465 7343 1226 6371 1744 656 3380 6272 3037 4601 1615 5168 5190 4836 9356 7298 4447 7757 3399 7902 1286 5257 6941 5587 1040 1603 40 6908 5716 2117 4598 7946 3705 8986 5792 3876 3085 2291 5099 2886 29 7438 7050 6992 7906 5493 5459 9136 3610 8320 4360 4268 5965 4926 8800 4770 8302 536 3947 4280 2225 9010 7953 1157 6184 3092 5747 3003 67 2135 8750 2530 5737 7575 178 8890 6607 4778 3784 8300 8659 2217 221 603 4551 9213 3267 8053 3370 2386 1047 5428 6664 4794 7469 9083 3390 5832 2334 1348 5098 292 2293 7325 4623 379 5914 7234 3015 4722 2962 2845 564 5637 9221 5203 2900 2019 1299 1982 7693 7356 2952 6419 9115 7904 5948 5388 9353 7186 5498 7410 3376 2493 5064 8671 7529 833 123 6350 4893 3237 3021 2496 9521 5549 4804 3168 5053 2385 6116 2976 1466 121 8284 263 9271 8144 5424 6138 1687 8090 639 8402 1383 2623 3273 8035 1947 6458 5235 369 4133 2645 9506 3745 1888 8690 3821 3000 238 439 2204 6457 7006 3869 3977 3385 7307 1323 5218 465 521 434 2539 1425 6040 8401 6225 7681 1829 8522 3515 3882 3093 4020 476 6866 4451 9420 6656 8173 5837 5010 503 8593 699 8394 6692 2261 4067 5625 3320 9116 8839 328 4183 4987 8569 3920 1302 4787 5113 2473 5160 4111 4881 1208 41 3512 341 460 8631 2016 5045 5842 2885 5030 2264 2606 4184 6874 4797 24 2928 1641 6332 7087 461 1117 8008 9503 1300 863 7176 5277 694 5028 3356 3173 3567 8564 7047 3698 5266 1351 4097 5370 6909 8730 4393 2349 4705 7782 8914 8904 301 8664 888 572 5362 4218 8031 2696 126 6932 9260 5611 3117 5352 1094 120 3926 4873 2405 9175 6502 3681 1479 3561 8020 2151 7460 7914 9442 4252 976 7525 479 9070 3723 104 9188 1130 8780 1798 7406 8470 6451 6831 9345 4177 2616 4817 8538 1766 103 9235 3106 9198 7848 6478 8572 5907 6125 7149 6796 210 1109 6329 790 7716 6634 329 2423 5301 5994 2982 3717 7696 5340 6623 3781 7560 8608 2895 357 1837 8065 2914 5628 6713 3716 437 2890 2776 593 6014 5592 6446 8510 4628 3444 26 5475 489 784 5355 3233 5603 5292 8266 3538 9499 1022 6337 2584 1871 7689 2259 5681 7303 4094 7530 3735 4970 8453 8123 5841 4430 5320 4932 6850 4425 4960 6828 7011 6232 6939 7408 7915 458 3076 6762 8911 992 2849 7127 1505 8076 8813 6002 3775 9457 9203 1560 3894 6701 1098 8891 2844 5843 517 3058 9035 5054 8281 3364 4738 6174 2608 9246 4855 1443 1464 5976 3790 2215 6427 8326 7276 5427 2684 4293 1310 2835 1363 206 8816 4154 8443 6568 1152 2939 3737 8889 5356 9474 378 5512 3152 7327 4180 945 1683 289 6435 1515 1677 594 9446 2098 6041 5708 1827 5374 4376 1488 3121 4233 290 4174 2984 5585 3211 2430 184 8616 5435 3897 5216 7999 214 7120 2315 6670 2177 1294 2595 9473 1304 6320 1439 5665 7619 5233 9462 752 7374 4791 3439 2679 2064 1545 2290 8684 3265 4613 4657 8378 6284 880 3854 3724 253 8900 4370 4140 8749 6962 1065 3902 2377 5959 1125 7615 2436 9240 7308 4402 7133 8332 9486 6247 7020 9091 4243 2446 8233 5021 6377 7032 4051 2855 568 3828 6978 3755 5260 8912 6412 798 7113 7947 4790 1721 6129 1722 2617 2317 4838 2760 5697 4750 403 5295 6680 8381 3806 3682 4729 3704 7630 5397 901 5253 4022 6888 8763 8785 2563 5313 2767 5228 8590 9057 6912 5389 1608 294 2867 5984 6185 4691 7175 7140 9485 1000 6365 2245 4777 1495 2170 1233 204 3607 1332 1598 6834 6627 9171 2673 1166 4480 8485 7152 8417 5608 8514 7825 3222 5215 2637 276 162 8647 4003 2756 8190 4039 6241 407 5161 7680 5578 6465 7317 9341 535 318 6983 7694 4443 5448 4586 6384 8589 1512 4758 1417 7997 9479 7713 349 8880 2287 324 1362 2403 6558 4138 8137 8046 4769 951 7582 3208 6870 1932 4288 8706 5176 4273 6899 8163 339 5572 6279 4505 847 2304 3455 3952 6498 5414 2870 7485 3486 8323 5042 4010 9018 7505 6382 3928 3429 4755 1824 4113 6098 7077 980 6560 1346 160 812 7160 5562 1633 5067 8449 7001 4035 614 8019 9467 4090 6529 3936 7725 1372 3837 3335 7638 8906 8915 8368 5546 7217 3971 5384 627 6523 9192 7397 7900 595 108 358 7830 7473 3506 3116 3438 7524 5727 794 3213 6728 5951 3435 5120 8794 6463 5993 6108 6998 8958 7515 7687 6658 8132 7545 1202 5800 8044 8942 246 4858 640 6235 4261 2792 8760 7090 6349 2309 4812 277 1845 2325 5618 8818 2793 7569 1367 8087 9139 9232 6923 5444 6439 3633 6614 5148 8992 9047 4061 5416 8367 6952 8493 7767 3131 2232 6884 4508 433 8261 681 5485 9258 9183 8180 7013 5365 5979 5614 8827 3189 3426 3067 2920 8292 3771 7497 2896 1088 4114 9519 2707 7189 2703 6110 1334 1943 5071 3559 9002 243 4980 2516 1901 2518 8893 2752 7129 5321 6137 1835 3450 467 4401 2972 2728 73 8027 1219 6246 5551 6 6963 5289 1884 3245 8530 4639 6851 8770 8424 2780 5540 3452 5911 6011 7373 5153 4595 3785 6625 5958 2456 2227 4848 12 882 7849 5110 2380 4967 4088 5195 4764 7139 8279 5525 9127 4772 1193 4725 4587 8223 362 6134 7143 413 698 3300 8465 8811 1409 2998 7377 1817 2588 7819 6317 2522 1834 370 3859 5670 563 4796 7134 3052 1301 3663 4707 4089 4423 690 4671 4118 8347 719 4064 6205 153 7414 4355 5679 2025 6308 499 1467 562 8851 6726 9080 3732 8194 3181 5753 7729 1164 2686 7758 7415 9118 3935 917 3979 6201 2237 3923 5184 9509 537 6822 7204 1823 9121 7890 8231 3006 5180 3584 703 2613 3371 3174 4762 9386 5096 5144 5501 651 8136 6867 3965 506 8486 3141 3314 8733 7792 2059 879 837 1215 2626 8356 5429 4460 7574 5925 3159 7071 7969 6489 667 4086 5101 1751 2635 601 7583 1115 6416 1730 8412 3138 7959 5872 7772 3695 3146 4059 2137 5943 7822 7807 971 1137 4007 7212 3898 9179 9390 1322 7719 8602 4656 5206 1009 4006 9289 4417 8972 115 1080 4902 9305 1020 7289 2131 187 60 9515 1964 5597 2116 8861 3091 2553 1084 4709 7975 4200 526 1663 5711 565 5136 1478 4166 3248 5764 6602 5660 8488 2404 6886 9143 5421 2722 7489 3659 4095 4910 8096 9306 1085 5251 6774 5806 406 711 146 8215 8555 4682 6855 5644 5069 528 3220 6236 3420 1291 8519 5211 9100 2547 4426 660 4699 3768 4859 2030 5700 6262 7952 2879 6494 3460 5868 1176 7967 6839 4149 9234 7037 6729 550 6079 4170 7322 9261 6472 1760 8513 4101 6776 6824 7670 716 6375 6477 6622 7724 39

… troncato (46.553 caratteri totali)

Output · run_log.txt

 44 76 154 176 180 198 233 239 275 284 312 334 350 379 439 465 476 503 572 593 594 614 627 640 681 698 719 917 971 1009 1080 1084 1085 1176 1248 1538 1613 1694 1738 1768 1789 1822 1843 1867 1905 2050 2068 2069 2102 2161 2314 2360 2445 2583 2624 2674 2787 2862 2875 2906 2918 2983 2993 2999 3156 3163 3225 3304 3312 3313 3342 3384 3405 3476 3539 3578 3597 3629 3638 3672 3688 3691 3696 3709 3740 3786 3791 3903 4029 4098 4196 4334 4445 4461 4471 4472 4477 4527 4534 4568 4645 4695 4882 5032 5049 5091 5118 5217 5487 5500 5523 5607 5638 5717 5765 5812 5815 5840 5882 5885 5906 5969 6042 6065 6112 6114 6121 6274 6282 6359 6405 6430 6551 6556 6583 6585 6681 6747 6753 6984 7056 7068 7108 7153 7220 7233 7235 7309 7507 7552 7602 7636 7637 7674 7769 7809 8051 8075 8108 8111 8166 8197 8251 8276 8366 8426 8451 8497 8504 8639 8645 8776 8932 8964 9086 9152 9173 9182 9220 9229 9244 9288 9298 9300 9304 9329 9362 9403 9455
 9417 9349 9292 9272 9257 9253 9142 9085 9060 9039 8977 8963 8887 8802 8699 8691 8653 8635 8539 8492 8478 8474 8435 8406 8337 8320 8302 8300 8284 8144 8090 8035 8031 8020 7914 7848 7716 7696 7560 7530 7408 7327 7308 7133 7113 7077 7001 6998 6923 6884 6851 6822 6774 6729 6622 6578 6538 6467 6448 6447 6381 6364 6296 6289 6186 6165 6104 6084 6067 5869 5830 5582 5497 5481 5353 5330 5310 5280 5240 5222 5175 5131 5075 5058 5056 5004 4963 4947 4890 4830 4655 4576 4546 4345 4295 4272 4259 4249 4123 4072 4047 3992 3968 3832 3826 3798 3691 3679 3616 3580 3568 3453 3406 3368 3346 3293 3285 3279 3277 3199 3194 3186 3123 3122 2949 2863 2791 2757 2724 2698 2687 2671 2662 2649 2559 2502 2499 2488 2387 2282 2216 2125 2045 2040 2037 2023 1997 1985 1963 1920 1879 1797 1782 1737 1660 1513 1492 1457 1437 1433 1366 1359 1354 1350 1328 1272 1236 1194 1138 1122 1079 1070 1013 867 760 749 605 600 488 484 469 417 414 384 373 320 303 218 201 82 81 20

Esegui nel browser · Pyodide

Mostra il codice sorgente (problem.py)

#http://rosalind.info/problems/lgis/

def lettura(filename):
    with open(filename) as f:
         _ = int(f.readline().replace("\n",""))  # count of elements, unused (len(n) is used instead)
         n = f.readline().replace("\n","").split()
    return n     

def gt(x, y):
   return int(x) > int(y);

def lt(x, y):
   return int(y) > int(x);

def main():
    funcs = (gt, lt)
    n = lettura("dataset.txt")
    for func in funcs:
        arr = []
        for i in range(len(n)):
            arr.append([0, 0])
        max_distance = 0;
        max_distance_i = 0;
        for i in range(len(n)):
            for j in range(i+1, len(n)):
                if func(n[j], n[i]):
                    old_distance = arr[i][0]
                    new_distance = arr[j][0]
                    if new_distance < old_distance+1:
                       arr[j][0] = old_distance+1; 
                       arr[j][1] = i; 
                       if old_distance+1 > max_distance:
                          max_distance = old_distance+1
                          max_distance_i = j

        prev = max_distance_i
        sol = []
        while(True):
           sol.insert(0, n[prev])
           if arr[prev][0] == 0:
             break
           prev = arr[prev][1]
        print(""," ".join(sol))
        #print("max_distance+1:"+str(max_distance+1)+"\n"+"sol.length:"+str(len(sol)))

# 44 76 154 176 180 198 233 239 275 284 312 334 350 379 439 465 476 503 572 593 594 614 627 640 681 698 719 917 971 1009 1080 1084 1085 1176 1248 1538 1613 1694 1738 1768 1789 1822 1843 1867 1905 2050 2068 2069 2102 2161 2314 2360 2445 2583 2624 2674 2787 2862 2875 2906 2918 2983 2993 2999 3156 3163 3225 3304 3312 3313 3342 3384 3405 3476 3539 3578 3597 3629 3638 3672 3688 3691 3696 3709 3740 3786 3791 3903 4029 4098 4196 4334 4445 4461 4471 4472 4477 4527 4534 4568 4645 4695 4882 5032 5049 5091 5118 5217 5487 5500 5523 5607 5638 5717 5765 5812 5815 5840 5882 5885 5906 5969 6042 6065 6112 6114 6121 6274 6282 6359 6405 6430 6551 6556 6583 6585 6681 6747 6753 6984 7056 7068 7108 7153 7220 7233 7235 7309 7507 7552 7602 7636 7637 7674 7769 7809 8051 8075 8108 8111 8166 8197 8251 8276 8366 8426 8451 8497 8504 8639 8645 8776 8932 8964 9086 9152 9173 9182 9220 9229 9244 9288 9298 9300 9304 9329 9362 9403 9455
# 9417 9349 9292 9272 9257 9253 9142 9085 9060 9039 8977 8963 8887 8802 8699 8691 8653 8635 8539 8492 8478 8474 8435 8406 8337 8320 8302 8300 8284 8144 8090 8035 8031 8020 7914 7848 7716 7696 7560 7530 7408 7327 7308 7133 7113 7077 7001 6998 6923 6884 6851 6822 6774 6729 6622 6578 6538 6467 6448 6447 6381 6364 6296 6289 6186 6165 6104 6084 6067 5869 5830 5582 5497 5481 5353 5330 5310 5280 5240 5222 5175 5131 5075 5058 5056 5004 4963 4947 4890 4830 4655 4576 4546 4345 4295 4272 4259 4249 4123 4072 4047 3992 3968 3832 3826 3798 3691 3679 3616 3580 3568 3453 3406 3368 3346 3293 3285 3279 3277 3199 3194 3186 3123 3122 2949 2863 2791 2757 2724 2698 2687 2671 2662 2649 2559 2502 2499 2488 2387 2282 2216 2125 2045 2040 2037 2023 1997 1985 1963 1920 1879 1797 1782 1737 1660 1513 1492 1457 1437 1433 1366 1359 1354 1350 1328 1272 1236 1194 1138 1122 1079 1070 1013 867 760 749 605 600 488 484 469 417 414 384 373 320 303 218 201 82 81 20


	                     
if __name__ == "__main__":
    # execute only if run as a script
    main()

Soluzione JavaScript

Esegui ora, live

Mostra il codice sorgente

// Longest Increasing Subsequence (Rosalind ID: LGIS) - soluzione
// JavaScript indipendente, non una trascrizione di problem.py: stesso
// algoritmo DP O(n^2) (per ogni coppia i<j con n[j] "successivo"
// rispetto a n[i] secondo il comparatore scelto, estende la catena più
// lunga terminante in i), eseguito due volte - una per la sottosequenza
// crescente, una per quella decrescente - riscritta in modo idiomatico
// per JS.
//
// Nota sul formato: come in inod.mjs/tree.mjs, problem.py fa
// print("", " ".join(sol)), che con il separatore di default di print
// produce uno SPAZIO INIZIALE prima della sequenza - riprodotto
// identico.
//
// Contratto: riceve il contenuto testuale di dataset.txt, restituisce
// l'output testuale (stessa forma dell'output Python).
function gt(x, y) {
  return x > y;
}

function lt(x, y) {
  return y > x;
}

function lettura(datasetText) {
  const righe = datasetText.split("\n").map((r) => r.replace(/\r$/, ""));
  const n = righe[1].trim().split(/\s+/);
  return n;
}

function risolviCatena(n, valori, func) {
  const len = n.length;
  const arr = Array.from({ length: len }, () => [0, 0]);
  let maxDistance = 0;
  let maxDistanceI = 0;

  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (func(valori[j], valori[i])) {
        const oldDistance = arr[i][0];
        const newDistance = arr[j][0];
        if (newDistance < oldDistance + 1) {
          arr[j][0] = oldDistance + 1;
          arr[j][1] = i;
          if (oldDistance + 1 > maxDistance) {
            maxDistance = oldDistance + 1;
            maxDistanceI = j;
          }
        }
      }
    }
  }

  let prev = maxDistanceI;
  const sol = [];
  while (true) {
    sol.unshift(n[prev]);
    if (arr[prev][0] === 0) break;
    prev = arr[prev][1];
  }
  return sol;
}

export default function solve(datasetText) {
  const n = lettura(datasetText);

  if (n.length === 0 || n.some((x) => !/^-?\d+$/.test(x))) {
    throw new Error("Input non valido: attesa una sequenza di interi");
  }

  const valori = n.map(Number);
  const funcs = [gt, lt];

  const righeOutput = funcs.map((func) => ` ${risolviCatena(n, valori, func).join(" ")}`);

  return `${righeOutput.join("\n")}\n`;
}