연속된 부분 배열의 최대합 (Kadane's Algorithm)

네!! 저는 요즘 ai랑 코드 테스트하는 재미에 푹 빠져있습니다!!!(누구한테 말하냐..?)

 

카다인 알고리즘으로 푸는 연속 부분 배열 최대 합

 

문제 설명

정수로 이루어진 배열 nums가 주어졌을 때, 연속된 부분 배열 중 가장 큰 합을 구하세요.

예시

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6

 

"연속된 부분 배열 중 가장 큰 합을 구하시오."

— 아니 나만 헷갈려? 연속된 부분 배열이라니… 연속된 숫자를 찾으라는 건가?  도대체 배열을 만들어야 하나? 

 

문제 설명이 좀 모호한거 같다고 그래서 ai한테 따져 물었더니 이렇게 말했다.

 

사실 문제의 진짜 의도는 이거야:
“주어진 배열 안에서, 숫자들이 연속해서 붙어 있는 모든 구간 중에서, 합이 제일 큰 구간을 찾아라.”
예를 들면, 길이가 1짜리인 [4] 같은 것도 가능하고, 전체 배열이 될 수도 있고, 중간 어딘가 끊긴 구간일 수도 있어.

 

 

 

1. 순진한 접근: 다 해보자!

"그냥 모든 조합 다 해보면 되지 않을까?" 맞긴 맞다. 하지만 이건 O(n^2) 이상 걸리는 방법이다. 배열 길이가 길어지면 또 컴퓨터가 숨을 참기 시작한다.

function maxSubArray(nums) {
  let maxSum = -Infinity;
  
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      maxSum = Math.max(maxSum, sum);
    }
  }
  
  return maxSum;
}

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1)

❌ 단점: 입력 배열이 길어지면 시간 초과가 날 수 있음.

 

 

2. 진짜(?) 개발자는 이렇게 푼다: 카다인(Kadane’s) 알고리즘

여기서 필요한 건 바로 카다인 알고리즘. 핵심은 간단하다. 지금까지 합친 결과가 음수가 되면 끊고 새로 시작하는 것!

연속된 배열이어야 하니까 중간에 합이 음수가 되면 전체 합에 독이 된다.

그래서 아예 끊어버리고 새롭게 시작! 이게 바로 카다인 알고리즘의 묘미다.(라고 ai 걔가 그러더라.. 걔는 참 말 잘해..얄밉게...)

function maxSubArray(nums) {
  let currentSum = 0;
  let maxSum = -Infinity;
  
  for (let i = 0; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]); // 지금까지의 합. 음수로 떨어지면 끊고 nums[i]부터 새로 시작
    maxSum = Math.max(maxSum, currentSum); // 지금까지 본 최대 합. 계속 업데이트
  }

  return maxSum;
}

console.log(maxSubArray([-2,1,-3,4,-1,2,1,-5,4])); // 6

• 시간 복잡도 O(n)
• 공간도 O(1)
• 추가 자료구조 불필요

 

!!! 여기서 갑자기 드는 의문

currentSum = Math.max(nums[i], currentSum + nums[i]);

 

이 코드를 그냥 음수가 아닐때 currentSum + nums[i]를 하는 건 어때?

그것도 어느 정도는 맞다. 이게 내가 진짜 진짜 헷갈렸던 부분인데 다시 문제로 들어가면 연속된 부분 배열이라는 명확한 명세가 있다.

그렇기 때문에 음수를 if 조건으로 구분하고 나머지 값만 더한다면 이 문제의 정확한 답이 될 수 없다는 것 

다시 초반에 제시되었던 예시를 확인해보면 

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

음수 빼고 양수만 더한다면:

• 양수만 뽑으면: 2 + 4 + 2 = 8

카다인 알고리즘은?

• [2, -1, 4] → 합: 5

 

이라는 말씀..

즉!! 중간에 끊기면 안된다는 말...

 

참고) 카다인 알고리즘의 흐름

 

 

 

• -3: currentSum = -3 → maxSum = -3
• -1: currentSum = max(-1, -3 + -1) = -1 → maxSum = -1
• 2: currentSum = max(2, -1 + 2) = 2 → maxSum = 2 ✅ 여기서 새 출발!
• -1: currentSum = max(-1, 2 + -1) = 1
• 4: currentSum = max(4, 1 + 4) = 5 → maxSum = 5
• -5: currentSum = 0
• 2: currentSum = max(2, 0 + 2) = 2

결론!! 최대 부분합은 [2, -1, 4] → 합 = 5

 

정리!

• 연속된 부분 배열? 카다인 알고리즘을 기억하자!
• 핵심은 지금까지의 합이 음수가 되는 순간, 새로 시작하는 것
• 시간 복잡도는 O(n) — 한 번만 순회하면 끝!

 

이제 이런 문제 나오면 당황하지 말고 카다인으로 시원하게 긁어주자! 힌트는 "연속된 부분배열의 합"!! (제발... 뇌야 기억 좀 해... 이젠 기억할 때도 됐어...)