918. Maximum Sum Circular Subarray
내 코드
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
maxSum = nums[0]
curSum = 0
for n in range(len(nums)*2):
if curSum <0:
curSum = 0
curSum += nums[n%len(nums)]
maxSum = max(maxSum, curSum)
return maxSum
이 코드는 틀렸음.
% 모듈러 연산으로 회전 행렬을 반영하고 있으나.
행렬 길이를 고려하고 있지 않음.
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
maxSum = nums[0]
curSum = 0
l = 0 # 윈도우의 왼쪽 포인터
for r in range(len(nums)*2):
# if curSum <0:
# curSum = 0
curSum += nums[r%len(nums)]
if r-l+1 > len(nums): # 행렬크기 넘어가면
curSum -= nums[l%len(nums)]
l+=1
if nums[l%len(nums)] < 0:
curSum -= nums[l%len(nums)]
l+=1
maxSum = max(maxSum, curSum)
return maxSum
고려해봤는데,
오답입..ㅠㅠ
https://youtu.be/fxT9KjakYPM?si=rsJ9Sk4RQcDyVVhV
class Solution:
def maxSubarraySumCircular(self, nums: List[int]) -> int:
# Kadane's Algorithm
# maximum subarry sum = sigma(nums) - minimum subarry sum
# = total - global minimum
globalMax, globalMin = nums[0], nums[0]
curMax, curMin = 0, 0
total = 0
for n in nums:
curMax = max(curMax + n, n)
curMin = min(curMin + n, n)
total += n
globalMax = max(globalMax, curMax)
globalMin = min(globalMin, curMin)
# 전체 배열이 최소 합일 경우, 원형 배열 고려 불가
# 모든 행렬의 요소가 음수 일 경우
if total == globalMin:
return globalMax
# 최대값은 직선 최대 부분 배열 합과 원형 최대 부분 배열 합 중 더 큰 값
return max(globalMax, total-globalMin)
'LeetCode > Top Interview 150' 카테고리의 다른 글
BST: 74. Search a 2D Matrix (1) | 2024.12.20 |
---|---|
35. Search Insert Position (0) | 2024.12.20 |
53. Maximum Subarray (0) | 2024.12.20 |
172. Factorial Trailing Zeroes (2) | 2024.12.18 |
66. Plus One (0) | 2024.12.18 |