53. Maximum Subarray
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
# Author: Huahua # Time complexity: O(n) # Space complexity: O(n) class Solution: def maxSubArray(self, nums: List[int]) -> int: @cache def dp(i: int) -> int: """Max subarray ends with nums[i].""" if i < 0: return 0 # Empty array. return nums[i] + max(0, dp(i - 1)) # Try all possible ending positions. return max(dp(i) for i in range(len(nums))) |
918. Maximum Sum Circular Subarray
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
# Author: Huahua # Time complexity: O(n) # Space complexity: O(n) class Solution: def maxSubarraySumCircular(self, nums: List[int]) -> int: n = len(nums) @cache def dp(i: int, s: int) -> int: """Max subarray ends with s * nums[i].""" if i < 0: return 0 # Empty array. # Append to max subbary ends with nums[i-1] or start a new one. return nums[i] * s + max(0, dp(i - 1, s)) max_p = max(dp(i, 1) for i in range(n)) max_n = max(dp(i, -1) for i in range(n)) return max_p if max_p < 0 else max(max_p, sum(nums) + max_n) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment