[LeetCode] 53. Maximum Subarray 풀이 (Java) | Kadane 알고리즘 핵심과 오답 정리

✔️ 오늘의 리트코드 공부 기록 – Maximum Subarray 

---

 

문제 요약 (Maximum Subarray )

정수 배열 nums가 주어질 때,
연속된 부분 배열(subarray) 중 합이 최대가 되는 값 을 구하는 문제

반드시 연속된 구간이어야 하고, 하나 이상의 원소를 포함해야 함

 

문제링크: https://leetcode.com/problems/maximum-subarray

 

---

 

🤔 처음 떠올린 접근 — 하지만 실패한 방법

처음 문제를 봤을 때 이렇게 생각했다.

 

“합이 음수가 되면 의미 없지 않나?”
“0부터 다시 시작하면 되겠네”

 

 

그래서 누적합(currentSum)이 음수가 되면 0으로 리셋하는 방식으로 접근했다.

int currentSum = 0;
int maxSum = 0;

 

❌ 문제점 1 — 모든 수가 음수인 경우를 고려하지 못함

 

이 방식은 모든 원소가 음수인 경우를 완전히 망친다.

 

예시:

[-3, -2, -5]

• currentSum은 계속 0으로 초기화
• maxSum도 0 유지
• ❌ 실제 정답은 -2

👉 원인은 명확했다.

• 0을 “아무것도 선택하지 않은 상태”로 허용해버림
• 하지만 문제는 반드시 하나 이상의 원소를 포함한 subarray를 요구함

📌 깨달음

• Maximum Subarray 문제에서 0을 기본값으로 두는 순간, 음수-only 케이스를 망친다.

---

🤔 두 번째 시도 — 그래도 어딘가 이상함

 

그래서 이번엔 이렇게 바꿨다.

int currentSum = nums[0];
int maxSum = 0;

 

❌ 문제점 2 — maxSum 초기값이 여전히 잘못됨

currentSum은 배열 값으로 시작했지만 maxSum은 여전히 0.

 

예시:

[-5]

• currentSum = -5
• maxSum = 0
• ❌ 결과: 0 (정답은 -5)

📌 깨달음

• currentSum과 maxSum은 같은 기준에서 시작해야 한다

---

🤔 세 번째 시도 — 거의 맞았지만 핵심을 놓침

if (currentSum + nums[i] < 0) {
    currentSum = 0;
}

 

❌ 문제점 3 — “0으로 리셋”이라는 사고 자체가 문제

이 코드에는 이런 암묵적 가정이 숨어 있었다.

“부분합은 음수가 되면 의미가 없다”

 

하지만 이 문제의 핵심은
합의 부호가 아니라, 미래에 도움이 되는지 여부다.

 

📌 깨달음

❌ “합이 음수인가?”

✔ “이전 합을 이어갈 가치가 있는가?”

---

🤔 네 번째 시도 — 판단 기준 자체가 틀림

if (nums[i] > 0) {
    currentSum = Math.max(sumValue, nums[i]);
} else {
    currentSum = sumValue;
}

 

❌ 문제점 4 — 값의 부호에 집착함

Kadane 알고리즘의 핵심 비교는 이거다.

이전 상태 + 현재 값
vs
현재 값 단독

 

그런데 여기서는 nums[i]가 양수냐 음수냐로 판단하고 있었다.

 

📌 깨달음

• 값의 부호는 중요하지 않다. 중요한 건 상태의 비교다.

---

😮 올바른 해결 — Kadane’s Algorithm

모든 시행착오를 정리하면,
결국 정답 로직은 이 한 줄로 귀결된다.

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

 

의미는 딱 이거다.

• 이전까지 쌓아온 합이 도움이 되면 이어가고
• 방해가 되면 과감히 버리고 새로 시작

참고) Kadane’s Algorithm은 👉 연속된 부분 배열 중 합의 최댓값을 O(n)에 구하는 알고리즘

 

💡 핵심 아이디어

이 문제의 본질은 이 질문 하나다.

이 숫자를 포함한 상태로 계속 가는 게 이득인가,
아니면 여기서 새로 시작하는 게 이득인가?

 

---

 

코드 (Java)

class Solution {

  public int maxSubArray(int[] nums) {
    int currentSum = 0;
    int maxSum = -1000000001;
    for (int num : nums) {
      int sumValue = currentSum + num;
      currentSum = Math.max(sumValue, num);
      maxSum = Math.max(currentSum, maxSum);
    }

    return maxSum;
  }
}

 

 

📈 Time / Space Complexity

• 시간: O(n)
• 공간: O(1)

---

 

📝 이번 문제에서 얻은 깨달음

• Maximum Subarray는 전형적인 상태 유지형 DP 문제
• “음수면 버린다”는 단순 규칙은 위험
• 버려야 하는 건 숫자(음수)가 아니라 👉 미래에 도움이 되지 않는 이전 상태

---

(번외) 회고 - 사고 가정의 전환 

이 문제에서의 실수는 구현 문제가 아니라 사고 가정을 어디에 두었느냐에서 시작됐다.
나는 처음에 이 문제를 “어떤 숫자를 고를까”라는 값 중심 문제로 바라봤고,
그래서 자연스럽게 “합이 음수면 의미 없다”, “0으로 리셋하면 된다”는 잘못된 가정에 빠졌다.

하지만 Maximum Subarray는 숫자를 고르는 문제가 아니라
이전 상태를 유지할지, 버릴지를 결정하는 문제였다.

 

❌ 잘못된 가정

“지금까지의 합이 음수면 의미 없다”

 

✅ 올바른 가정

“i에서 끝나는 최적의 선택은 딱 두 가지뿐이다”

 

1. 이전까지의 최적 상태에 nums[i]를 이어붙인다.
2. nums[i] 하나로 새로 시작한다.

이 문제를 통해 배운 가장 큰 교훈은 분명하다.

알고리즘 문제에서 막힐 때, 먼저 의심해야 할 것은 코드가 아니라
내가 문제를 어떤 가정 위에서 해석하고 있는가라는 점이다.