在黑客级别上,测试用例给出运行时错误,但在本地机器上给出正确的输出

2024-06-17 16:34:17 发布

您现在位置:Python中文网/ 问答频道 /正文

这段代码在hacker rank上给出了这个测试用例的运行时错误,但当我在本地机器上用相同的测试用例运行这段代码时,它会给出正确的输出

n = int(input())
li = [int(x) for x in input().split()]
se = set()
se1 = set()
for x in range(n):
    for y in range(x, n):
        if tuple(li[x:y+1]) not in se1:
                se.add(len(li[x:y+1]) * min(li[x:y+1]))
                se1.add(tuple(li[x:y+1]))
print(max(se))

测试用例

1000
8505 7916 8460 4200 7096 2044 5971 3746 7934 1043 9114 7722 5284 4324 1603 8290 1460 5855 1989 7322 7962 2004 2885 6643 543 240 6303 999 4967 6429 6653 9824 697 1466 4025 4146 9862 6348 4244 7797 3743 3358 5519 9028 4034 3474 3670 5494 5681 2011 9169 3643 4015 8406 6638 910 8646 2941 8261 3613 5722 4915 3437 6420 6381 3814 6918 2595 162 1162 392 3906 872 2263 9286 4906 2089 9308 6752 7770 1320 5921 1414 1687 679 8052 2598 9325 7346 7211 9290 3068 2126 9080 5840 4859 2894 9110 7455 9409 272 4199 3315 7496 2815 8953 2402 4904 8261 5507 2675 5933 7780 441 7621 8460 4845 6571 4137 2191 3782 3428 1612 2261 8860 7452 7120 1754 6563 927 7515 3187 1479 7182 684 4294 6135 9438 9198 749 1297 8225 6682 9078 8666 4303 3890 3512 874 8027 5703 1009 7807 3667 3270 6667 1120 6742 4774 4035 4022 2289 7222 5501 9472 4258 6147 1959 49 5345 2708 1346 3571 9391 6776 8589 46 666 2101 7273 5046 4157 8282 9205 7824 1552 5873 5296 8294 6999 9331 2316 5640 2906 4169 5112 3516 316 3424 9917 2014 6132 7616 1937 1875 4392 526 1922 1411 2628 9195 2809 3137 3829 2014 7313 5381 7887 2610 27 1238 8293 8696 6879 7551 2865 1991 1068 3182 1767 7337 1548 4252 4953 3485 6127 9346 4011 4401 7109 2991 9948 9918 6128 3777 1932 9794 5510 6172 2404 5538 7410 7049 4234 4289 4601 3451 2633 2021 2985 4400 9358 4533 8652 4312 8018 1132 10 2030 1885 7119 5021 1834 3389 7502 1963 5321 3648 7474 1493 6052 9364 5256 9453 9950 9545 4054 3401 2178 2427 2739 2931 8138 7272 7935 8802 5291 9067 8812 3673 953 2283 5046 9139 5672 8900 1102 7345 2548 4928 5191 4952 4292 447 4406 594 6344 4812 348 8523 7240 3087 7806 1730 359 5741 532 2002 1161 5696 5675 2114 7979 722 7605 3 5974 8707 7348 8523 9988 8891 3475 632 9338 7881 1227 5683 9046 1575 558 2638 4662 8364 4368 1373 457 4900 3376 1618 596 5403 3732 4927 2477 1337 4930 8452 6397 8630 6975 6385 7522 6802 7017 3212 1036 4596 5247 82 6171 5805 2720 7185 521 7088 4911 979 8340 4639 2597 5288 6394 2682 215 8872 371 1497 3676 6768 6479 651 9505 353 3805 2875 3566 4841 7471 5165 4923 9995 971 3995 3532 7844 7435 4795 5175 2127 9434 7773 7415 5829 6807 3982 1053 7178 5479 4729 299 8311 1732 6156 8664 5537 9031 8582 6731 2855 3748 8006 9202 1071 2002 2734 8915 5789 7530 4091 7917 3316 8216 5332 5497 5023 9315 6550 8553 1146 1279 5204 5809 3011 1361 4474 4901 6744 3056 1632 9599 6804 9638 8801 7875 1640 7888 3143 3782 1770 7234 1699 5086 5450 7031 6936 6825 2698 3486 5378 197 4766 6935 6006 4129 8296 480 5382 5040 9889 7014 992 3045 6653 6145 7273 4645 385 416 8427 2155 4002 6478 3594 9452 3510 530 2629 2560 4016 4359 9109 5134 1294 5116 5616 9590 1948 998 983 8189 4365 8327 1235 7370 824 4860 8367 1210 5276 3147 9717 9278 9625 3311 5082 9487 193 4063 2048 562 8422 7509 5696 9717 2625 7664 5659 926 5015 2994 5467 9380 7673 6702 6750 8498 1562 5117 6060 3190 8264 5777 8820 4242 5441 3902 3729 5634 7965 2129 6196 2740 9639 8245 2457 8616 2261 4468 9542 7276 7463 1362 3008 5136 8064 9758 9986 5979 1228 6046 5521 5844 1824 4342 86 3617 4596 168 9251 2562 2297 1800 5302 1936 45 4111 6905 2306 8579 2799 5935 2394 4161 8943 3883 8578 5054 3869 909 2634 6268 6430 8478 4444 7124 4917 8061 1721 1437 3664 635 3734 5464 2289 2023 5509 6400 8928 4168 1331 1727 103 78 5889 9046 3961 4467 452 4182 5376 3086 6802 8158 1565 1246 5283 2834 5659 7004 4271 9324 7639 4357 4788 6280 2732 298 2680 1660 818 363 9740 921 441 5629 6319 754 6448 6772 1289 8176 9858 8091 6334 7775 5690 7969 6961 1349 1325 7584 673 8964 8294 1814 1596 1026 8464 4276 2687 9282 992 8779 6555 7785 760 9226 4892 7208 5998 6181 1736 2209 624 4422 6336 6314 2392 9650 4016 3717 7234 1041 9034 5528 2855 630 6555 1319 1259 5594 6953 2251 4373 3508 6388 5133 2735 1280 8693 5085 7461 429 3646 4438 1203 6335 752 3595 5985 1120 7313 3219 2162 2699 5100 5017 3329 8007 2689 940 9953 9642 3191 678 9503 5932 2163 8590 7212 856 27 1026 7637 3674 5464 8840 6361 2568 8788 2346 3689 2453 1917 2203 5152 7017 3572 4833 1376 6261 5774 1329 2256 8965 2007 1759 1249 4170 6701 8462 1378 6728 9488 9015 6754 1304 4208 3115 3872 2996 5461 3913 5449 7379 6116 6953 748 9689 1786 2125 2302 7560 3454 4558 2878 1814 2669 4127 5984 5722 2589 3715 2451 8429 9082 5557 6085 3290 8673 6310 2638 486 223 4439 4217 2692 1392 1318 8733 3179 3443 1035 739 3249 1946 3617 5063 967 4097 7400 6690 3038 1115 9141 1468 197 1050 3905 9840 9723 215 8830 6562 6791 3270 779 9483 4662 8449 4568 4193 1892 5603 1285 1494 3901 1254 2909 4869 5351 309 1559 8390 7776 7052 6210 4326 8102 115 518 4178 6683 9348 740 3474 2618 7871 9309 3633 6321 3877 7826 4565 5832 5463 6059 9734 6718 8969 4603 8421 5630 6162 6811 3407 9566 9373 4085 7668 5841 4603 1846 2524 3951 8938 2350 6570 6810 8011 6555 9483 1888 733 4048 4072 6197 108 3806 9267 5429 8409 7688 1059 923 852 818 489 225 4903 4510 2418 9506 2708 4942 3458 1647 3644 6380 4809 1655 9287 4292 9895 20 8340 3968 2569 4800 7774 1836 6581 2536 5877 7641 9811 6729 4811 6653

Tags: 代码inaddforinput测试用例rangeli
1条回答
网友
1楼 · 发布于 2024-06-17 16:34:17

我优化了您的算法,删除了集合的使用,并通过计算滚动最小值改进了子范围的最小值计算。我的算法的运行时间是O(N^2)

您的算法具有O(N^3)复杂性,因为有两个循环(每个O(N)),然后在每个循环内添加到集合,计算最小值和切片都需要O(N)时间(因为添加一个长度为O(N)的元组到集合还需要对其所有元素进行O(N)哈希操作)。所以,若你们不使用集合,你们的算法可能会更快,因为向集合中添加元组需要和再次计算最小值相同的时间。另外,您不需要将结果存储在se集中,您只需在途中计算最大值即可

Try it online!

n, l = int(input()), list(map(int, input().split()))
maxv = None
for i in range(n):
    minv, maxv = l[i], l[i] if maxv is None else maxv
    for j in range(i, n):
        minv = min(minv, l[j])
        maxv = max(maxv, (j - i + 1) * minv)
print(maxv)

输入:

1000
8505 7916 8460 4200 7096 2044 5971 3746 7934 1043 9114 7722 5284 4324 1603 8290 1460 5855 1989 7322 7962 2004 2885 6643 543 240 6303 999 4967 6429 6653 9824 697 1466 4025 4146 9862 6348 4244 7797 3743 3358 5519 9028 4034 3474 3670 5494 5681 2011 9169 3643 4015 8406 6638 910 8646 2941 8261 3613 5722 4915 3437 6420 6381 3814 6918 2595 162 1162 392 3906 872 2263 9286 4906 2089 9308 6752 7770 1320 5921 1414 1687 679 8052 2598 9325 7346 7211 9290 3068 2126 9080 5840 4859 2894 9110 7455 9409 272 4199 3315 7496 2815 8953 2402 4904 8261 5507 2675 5933 7780 441 7621 8460 4845 6571 4137 2191 3782 3428 1612 2261 8860 7452 7120 1754 6563 927 7515 3187 1479 7182 684 4294 6135 9438 9198 749 1297 8225 6682 9078 8666 4303 3890 3512 874 8027 5703 1009 7807 3667 3270 6667 1120 6742 4774 4035 4022 2289 7222 5501 9472 4258 6147 1959 49 5345 2708 1346 3571 9391 6776 8589 46 666 2101 7273 5046 4157 8282 9205 7824 1552 5873 5296 8294 6999 9331 2316 5640 2906 4169 5112 3516 316 3424 9917 2014 6132 7616 1937 1875 4392 526 1922 1411 2628 9195 2809 3137 3829 2014 7313 5381 7887 2610 27 1238 8293 8696 6879 7551 2865 1991 1068 3182 1767 7337 1548 4252 4953 3485 6127 9346 4011 4401 7109 2991 9948 9918 6128 3777 1932 9794 5510 6172 2404 5538 7410 7049 4234 4289 4601 3451 2633 2021 2985 4400 9358 4533 8652 4312 8018 1132 10 2030 1885 7119 5021 1834 3389 7502 1963 5321 3648 7474 1493 6052 9364 5256 9453 9950 9545 4054 3401 2178 2427 2739 2931 8138 7272 7935 8802 5291 9067 8812 3673 953 2283 5046 9139 5672 8900 1102 7345 2548 4928 5191 4952 4292 447 4406 594 6344 4812 348 8523 7240 3087 7806 1730 359 5741 532 2002 1161 5696 5675 2114 7979 722 7605 3 5974 8707 7348 8523 9988 8891 3475 632 9338 7881 1227 5683 9046 1575 558 2638 4662 8364 4368 1373 457 4900 3376 1618 596 5403 3732 4927 2477 1337 4930 8452 6397 8630 6975 6385 7522 6802 7017 3212 1036 4596 5247 82 6171 5805 2720 7185 521 7088 4911 979 8340 4639 2597 5288 6394 2682 215 8872 371 1497 3676 6768 6479 651 9505 353 3805 2875 3566 4841 7471 5165 4923 9995 971 3995 3532 7844 7435 4795 5175 2127 9434 7773 7415 5829 6807 3982 1053 7178 5479 4729 299 8311 1732 6156 8664 5537 9031 8582 6731 2855 3748 8006 9202 1071 2002 2734 8915 5789 7530 4091 7917 3316 8216 5332 5497 5023 9315 6550 8553 1146 1279 5204 5809 3011 1361 4474 4901 6744 3056 1632 9599 6804 9638 8801 7875 1640 7888 3143 3782 1770 7234 1699 5086 5450 7031 6936 6825 2698 3486 5378 197 4766 6935 6006 4129 8296 480 5382 5040 9889 7014 992 3045 6653 6145 7273 4645 385 416 8427 2155 4002 6478 3594 9452 3510 530 2629 2560 4016 4359 9109 5134 1294 5116 5616 9590 1948 998 983 8189 4365 8327 1235 7370 824 4860 8367 1210 5276 3147 9717 9278 9625 3311 5082 9487 193 4063 2048 562 8422 7509 5696 9717 2625 7664 5659 926 5015 2994 5467 9380 7673 6702 6750 8498 1562 5117 6060 3190 8264 5777 8820 4242 5441 3902 3729 5634 7965 2129 6196 2740 9639 8245 2457 8616 2261 4468 9542 7276 7463 1362 3008 5136 8064 9758 9986 5979 1228 6046 5521 5844 1824 4342 86 3617 4596 168 9251 2562 2297 1800 5302 1936 45 4111 6905 2306 8579 2799 5935 2394 4161 8943 3883 8578 5054 3869 909 2634 6268 6430 8478 4444 7124 4917 8061 1721 1437 3664 635 3734 5464 2289 2023 5509 6400 8928 4168 1331 1727 103 78 5889 9046 3961 4467 452 4182 5376 3086 6802 8158 1565 1246 5283 2834 5659 7004 4271 9324 7639 4357 4788 6280 2732 298 2680 1660 818 363 9740 921 441 5629 6319 754 6448 6772 1289 8176 9858 8091 6334 7775 5690 7969 6961 1349 1325 7584 673 8964 8294 1814 1596 1026 8464 4276 2687 9282 992 8779 6555 7785 760 9226 4892 7208 5998 6181 1736 2209 624 4422 6336 6314 2392 9650 4016 3717 7234 1041 9034 5528 2855 630 6555 1319 1259 5594 6953 2251 4373 3508 6388 5133 2735 1280 8693 5085 7461 429 3646 4438 1203 6335 752 3595 5985 1120 7313 3219 2162 2699 5100 5017 3329 8007 2689 940 9953 9642 3191 678 9503 5932 2163 8590 7212 856 27 1026 7637 3674 5464 8840 6361 2568 8788 2346 3689 2453 1917 2203 5152 7017 3572 4833 1376 6261 5774 1329 2256 8965 2007 1759 1249 4170 6701 8462 1378 6728 9488 9015 6754 1304 4208 3115 3872 2996 5461 3913 5449 7379 6116 6953 748 9689 1786 2125 2302 7560 3454 4558 2878 1814 2669 4127 5984 5722 2589 3715 2451 8429 9082 5557 6085 3290 8673 6310 2638 486 223 4439 4217 2692 1392 1318 8733 3179 3443 1035 739 3249 1946 3617 5063 967 4097 7400 6690 3038 1115 9141 1468 197 1050 3905 9840 9723 215 8830 6562 6791 3270 779 9483 4662 8449 4568 4193 1892 5603 1285 1494 3901 1254 2909 4869 5351 309 1559 8390 7776 7052 6210 4326 8102 115 518 4178 6683 9348 740 3474 2618 7871 9309 3633 6321 3877 7826 4565 5832 5463 6059 9734 6718 8969 4603 8421 5630 6162 6811 3407 9566 9373 4085 7668 5841 4603 1846 2524 3951 8938 2350 6570 6810 8011 6555 9483 1888 733 4048 4072 6197 108 3806 9267 5429 8409 7688 1059 923 852 818 489 225 4903 4510 2418 9506 2708 4942 3458 1647 3644 6380 4809 1655 9287 4292 9895 20 8340 3968 2569 4800 7774 1836 6581 2536 5877 7641 9811 6729 4811 6653

输出:

85175

相关问题 更多 >