{"topic":{"id":13271,"title":"哪位大佬能帮我看看为什么 Leetcode 918. Maximum Sum Circular Subarray 我的答案不对","slug":"topic","categoryId":4,"createdAt":"2024-08-16 12:58:08.754702","bumpedAt":"2024-08-16 13:32:26.219146","views":119,"postsCount":2,"highestPostNumber":2,"likeCount":0,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":"https://leetcode.com/problems/maximum-sum-circular-subarray/?envType=study-plan-v2&envId=top-interview-150 Wrong Answer 107 / 112 testcases passed nums=[52,183,124,154,-170,-191,-240,107,-178,171,75,186,-125,61,-298,…","deletedAt":null,"isAnonymous":false,"category":{"id":4,"name":"谈笑风生","slug":"general","color":"25AAE2"},"author":{"id":4668,"username":"IO","name":null,"avatarUrl":"/uploads/image/86/f2/86f267c0aaa73835a999b7cc3a7e7a701605574eda9a2c2a56f5ddbbba64d1a9.avif"},"tags":[]},"posts":[{"id":38766,"postNumber":1,"raw":"https://leetcode.com/problems/maximum-sum-circular-subarray/?envType=study-plan-v2&envId=top-interview-150\n\n\n### [color=red]Wrong Answer[/color] \n107 / 112 testcases passed\n```\nnums=[52,183,124,154,-170,-191,-240,107,-178,171,75,186,-125,61,-298,284,21,-73,-294,253,146,248,-248,127,26,289,118,-22,-300,26,-116,-113,-44,29,252,-278,47,254,-106,246,-275,42,257,15,96,-298,-69,-104,-239,-95,-4,76,-202,156,-14,-178,188,-84,78,-195,-125,28,109,125,-25,-53,58,287,55,-296,198,281,53,-160,146,298,25,-41,-3,27,-242,169,287,-281,19,91,213,115,211,-218,124,-25,-272,278,296,-177,-166,-192,97,-49,-25,168,-81,6,-94,267,293,146,-1,-258,256,283,-156,197,28,78,267,-151,-230,-66,100,-94,-66,-123,121,-214,-182,187,65,-186,215,273,243,-99,-76,178,59,190,279,300,217,67,-117,170,163,153,-37,-147,-251,296,-176,117,68,258,-159,-300,-36,-91,-60,195,-293,-116,208,175,-100,-97,188,79,-270,80,100,211,112,264,-217,-142,5,105,171,-264,-247,138,275,227,-86,30,-219,153,10,-66,267,22,-56,-70,-234,-66,89,182,110,-146,162,-48,-201,-240,-225,-15,-275,129,-117,28,150,84,-264,249,-85,70,-140,-259,26,162,5,-203,143,184,101,140,207,131,177,274,-178,-79,14,-36,104,52,31,257,273,-52,74,276,104,-133,-255,188,-252,229,200,-74,-39,-250,142,-201,-196,-43,-40,255,-149,-299,-197,-175,-96,-155,-196,-24,12,79,71,-144,-59,-120,227,-256,-163,-297,116,286,-283,-31,-221,-41,121,-170,160,205,8,88,25,-272,-107,292,-180,299,94,-97,-81,-134,37,238]\n```\n\nView less\n\nUse Testcase\n\nOutput\n\n5519\n\nExpected\n\n5803\n\n窝的代码：\n```python\nclass Solution:\n def maxSubarraySumCircular(self, nums: List[int]) -> int:\n L = len(nums)\n subarr_sum = 0\n max_subarr_sum = float('-inf')\n subar_len = 0\n SUBARR_LEN_MAX = L\n # find max-sum sub-array of max length `SUBARR_LEN_MAX`\n for i in range(2 * L):\n n = nums[i % L]\n subar_len += 1\n if subar_len > SUBARR_LEN_MAX:\n to_remove_start_index = i - SUBARR_LEN_MAX\n subarr_sum -= nums[to_remove_start_index % L]\n subar_len -= 1\n # remove leading negative items\n for j in range(to_remove_start_index + 1, i):\n if nums[j % L] < 0:\n subarr_sum -= nums[j % L]\n subar_len -= 1\n else:\n break\n subarr_sum += n\n if subarr_sum > max_subarr_sum:\n max_subarr_sum = subarr_sum\n if subarr_sum < 0:\n subarr_sum = 0\n subar_len = 0\n return max_subarr_sum\n\n```\n\n\n我的思路是考虑找 `nums * 2` 的长度最大为 `len(nums)` 的 max-sum sub-arrary，但是只通过了 107 / 112 testcases passed\n\n谢谢！","cooked":"

https://leetcode.com/problems/maximum-sum-circular-subarray/?envType=study-plan-v2&envId=top-interview-150

Wrong Answer

107 / 112 testcases passed

nums=[52,183,124,154,-170,-191,-240,107,-178,171,75,186,-125,61,-298,284,21,-73,-294,253,146,248,-248,127,26,289,118,-22,-300,26,-116,-113,-44,29,252,-278,47,254,-106,246,-275,42,257,15,96,-298,-69,-104,-239,-95,-4,76,-202,156,-14,-178,188,-84,78,-195,-125,28,109,125,-25,-53,58,287,55,-296,198,281,53,-160,146,298,25,-41,-3,27,-242,169,287,-281,19,91,213,115,211,-218,124,-25,-272,278,296,-177,-166,-192,97,-49,-25,168,-81,6,-94,267,293,146,-1,-258,256,283,-156,197,28,78,267,-151,-230,-66,100,-94,-66,-123,121,-214,-182,187,65,-186,215,273,243,-99,-76,178,59,190,279,300,217,67,-117,170,163,153,-37,-147,-251,296,-176,117,68,258,-159,-300,-36,-91,-60,195,-293,-116,208,175,-100,-97,188,79,-270,80,100,211,112,264,-217,-142,5,105,171,-264,-247,138,275,227,-86,30,-219,153,10,-66,267,22,-56,-70,-234,-66,89,182,110,-146,162,-48,-201,-240,-225,-15,-275,129,-117,28,150,84,-264,249,-85,70,-140,-259,26,162,5,-203,143,184,101,140,207,131,177,274,-178,-79,14,-36,104,52,31,257,273,-52,74,276,104,-133,-255,188,-252,229,200,-74,-39,-250,142,-201,-196,-43,-40,255,-149,-299,-197,-175,-96,-155,-196,-24,12,79,71,-144,-59,-120,227,-256,-163,-297,116,286,-283,-31,-221,-41,121,-170,160,205,8,88,25,-272,-107,292,-180,299,94,-97,-81,-134,37,238]\n

View less

Use Testcase

Output

5519

Expected

5803

窝的代码：

class Solution:\n    def maxSubarraySumCircular(self, nums: List[int]) -> int:\n        L = len(nums)\n        subarr_sum = 0\n        max_subarr_sum = float('-inf')\n        subar_len = 0\n        SUBARR_LEN_MAX = L\n        # find max-sum sub-array of max length `SUBARR_LEN_MAX`\n        for i in range(2 * L):\n            n = nums[i % L]\n            subar_len += 1\n            if subar_len > SUBARR_LEN_MAX:\n                to_remove_start_index = i - SUBARR_LEN_MAX\n                subarr_sum -= nums[to_remove_start_index % L]\n                subar_len -= 1\n                # remove leading negative items\n                for j in range(to_remove_start_index + 1, i):\n                    if nums[j % L] < 0:\n                        subarr_sum -= nums[j % L]\n                        subar_len -= 1\n                    else:\n                        break\n            subarr_sum += n\n            if subarr_sum > max_subarr_sum:\n                max_subarr_sum = subarr_sum\n            if subarr_sum < 0:\n                subarr_sum = 0\n                subar_len = 0\n        return max_subarr_sum\n\n

我的思路是考虑找 nums * 2 的长度最大为 len(nums) 的 max-sum sub-arrary，但是只通过了 107 / 112 testcases passed

谢谢！

\n","createdAt":"2024-08-16 12:58:08.948762","updatedAt":"2024-08-16 12:58:08.948762","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":174,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4668,"username":"IO","name":null,"avatarUrl":"/uploads/image/86/f2/86f267c0aaa73835a999b7cc3a7e7a701605574eda9a2c2a56f5ddbbba64d1a9.avif","admin":true,"moderator":false,"signatureRaw":"","signatureCooked":null}},{"id":38769,"postNumber":2,"raw":"看了一下标准答案，对于非全非负的 arrary，答案是 sum(nums) - find_min_subarrary(nums) ，巧妙啊，但是我不知道我这样机械的方式怎么错了，也没法可视化得看","cooked":"

看了一下标准答案，对于非全非负的 arrary，答案是 sum(nums) - find_min_subarrary(nums) ，巧妙啊，但是我不知道我这样机械的方式怎么错了，也没法可视化得看

\n","createdAt":"2024-08-16 13:32:26.219146","updatedAt":"2024-08-16 13:32:26.219146","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":55,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4668,"username":"IO","name":null,"avatarUrl":"/uploads/image/86/f2/86f267c0aaa73835a999b7cc3a7e7a701605574eda9a2c2a56f5ddbbba64d1a9.avif","admin":true,"moderator":false,"signatureRaw":"","signatureCooked":null}}],"hasMore":false,"lastReadPostNumber":1,"hasUrlPostNumber":false}