53. Maximum Subarray ☆☆★

53. Maximum Subarray

 

좋아요! 먼저 주신 코드는 Kadane's Algorithm 기반의 O(n) 시간 복잡도 풀이예요.
아주 잘 작성하셨고, 여기에 상세 주석을 달아드릴게요.
그 다음 Follow-up: Divide and Conquer 방식도 자세히 설명드릴게요.

---

✅ Kadane's Algorithm 풀이 (O(n)) + 주석

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 현재까지 탐색한 부분에서의 최대 연속합을 저장할 변수
        curSum = maxSum = nums[0]  # 초기값: 첫 번째 원소

        # 두 번째 원소부터 끝까지 순회
        for r in range(1, len(nums)):
            # 현재까지의 누적 합이 음수면, 누적할 가치가 없으므로 0으로 리셋
            if curSum < 0:
                curSum = 0

            # 현재 값을 누적
            curSum += nums[r]

            # 최대합 갱신
            maxSum = max(maxSum, curSum)

        return maxSum

---

📌 핵심 로직 요약

• 음수만 누적되고 있다면, 그 서브배열은 버리고 다시 시작하는 게 낫다.
• 따라서 누적합이 음수가 되는 순간 버리고 0부터 다시 시작.
• 이렇게 하면 O(n) 시간에 전체 배열 중 가장 큰 연속합을 구할 수 있음.

---

✅ Follow-up: Divide and Conquer 방식 설명

Kadane은 O(n)이지만, 분할정복(divide and conquer) 방식은 다음과 같은 아이디어를 사용합니다:

👇 방법 개요:

1. 배열을 중간 기준으로 좌우 두 부분으로 나눔
2. 세 가지 경우 중 최대값을 구함:
   • 왼쪽 서브배열의 최대 연속합
   • 오른쪽 서브배열의 최대 연속합
   • 가운데를 걸치는 최대 연속합
3. 이 과정을 재귀적으로 반복

---

📌 시간 복잡도:

• 이 방식은 O(n log n)
  → 매 분할마다 전체 탐색 (O(n)) + 분할 log n 단계

---

✅ Divide and Conquer 코드 예시:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def helper(left, right):
            if left == right:
                return nums[left]

            mid = (left + right) // 2

            # 왼쪽, 오른쪽 최대값
            left_max = helper(left, mid)
            right_max = helper(mid+1, right)

            # 가운데 걸치는 최대 연속합 계산
            left_sum = float('-inf')
            cur = 0
            for i in range(mid, left - 1, -1):
                cur += nums[i]
                left_sum = max(left_sum, cur)

            right_sum = float('-inf')
            cur = 0
            for i in range(mid + 1, right + 1):
                cur += nums[i]
                right_sum = max(right_sum, cur)

            cross_max = left_sum + right_sum

            return max(left_max, right_max, cross_max)

        return helper(0, len(nums) - 1)

---

✅ 두 방법 비교:

방법	시간복잡도	공간복잡도	특징
Kadane's Algorithm	O(n)	O(1)	가장 효율적. 반복문 기반
Divide and Conquer	O(n log n)	O(log n) (재귀 콜스택)	알고리즘 원리 연습에 좋음. 경계값 처리가 중요

---

---

---

내 두번째 풀이

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 연속하는 subarry
        maxSum = subSum = nums[0]
        l = 0
        for r in range(1, len(nums)):
            subSum += nums[r]

            while l<r and subSum <= 0:
                subSum -= nums[l]
                l+=1
            maxSum = max(maxSum, subSum)

        return maxSum

 

이 코드가 틀리는 이유는 최대 부분합 문제(Maximum Subarray) 의 가장 대표적인 풀이인 카데인 알고리즘(Kadane's Algorithm) 과 달리, 부분합이 음수가 될 때 이전 값들을 제거하는 투포인터 방식을 사용했기 때문입니다.

 

이 문제는 반드시 모든 원소를 연속적으로 더하면서,

음수가 될 때// 현재까지의 부분합을 초기화(0 또는 현재 값으로 reset)하는 방식으로 풀어야 합니다.

---

❌ 문제점:

• 현재 코드의 문제:
  • 부분합이 음수가 될 때 왼쪽에서부터 한 원소씩 제거함으로써, 중간에 최적의 해를 놓칠 수 있음.
  • 예를 들어, 중간에 음수가 크게 포함되어 있고, 이 음수를 제거하기 위해 왼쪽을 계속 당기다가, 실제로 최적인 부분합까지 놓쳐버릴 수 있습니다.

🟢 올바른 접근 (카데인 알고리즘):

1. 현재 부분합(subSum)을 계속 더하면서 음수가 될 때마다, 다음 원소부터 새롭게 시작합니다.
2. 매번 더한 값이 최대값(maxSum)보다 크면 갱신합니다.

---

✅ 정답 코드:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = subSum = nums[0]

        for num in nums[1:]:
            subSum = max(num, subSum + num)  # 이전 부분합이 음수면 현재 숫자에서 새로 시작
            maxSum = max(maxSum, subSum)     # 최대값 갱신

        return maxSum

---

📌 예시로 이해하기:

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

과정:
-2 → subSum=-2, maxSum=-2
 1 → subSum=1,  maxSum=1
-3 → subSum=-2, maxSum=1
 4 → subSum=4,  maxSum=4
-1 → subSum=3,  maxSum=4
 2 → subSum=5,  maxSum=5
 1 → subSum=6,  maxSum=6
-5 → subSum=1,  maxSum=6
 4 → subSum=5,  maxSum=6 (최종 최대합: 6)

---

💡 핵심 포인트:

• Sliding window는 양수만 있거나 특정 조건에서만 유효하며, 일반적인 최대 서브 배열 합 문제에는 적합하지 않습니다.
• 음수를 만나도 무조건 창을 줄이면 안 되고, 대신 현재까지의 합이 음수면 전체를 버리고 새롭게 시작해야 정확한 최대값을 얻을 수 있습니다.

 

🔑 결론:

최대 부분합 문제의 정석은 Kadane’s Algorithm 이며, 투포인터 방식으로 접근하면 최적의 해를 놓칠 수 있습니다. 위의 수정된 코드를 사용하면 정상적으로 정답 처리가 됩니다.

 

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 서브어레이는.. 연속적인 값.. 이것의 합이 최대가 되려면.
        # 합이 - 되면 시작 인덱스를 다시 시작해야
        maxSum = subSum = nums[0] # 초기값은 0이 아니라, 배열의 첫값, 왜냐 -값이 있을수도있어서
        for n in range(1, len(nums)):
            if subSum <0:
                subSum = 0
            subSum += nums[n]
            maxSum = max(maxSum, subSum)
        return maxSum