CodeUtility
개발자의 삶을 더 쉽게!
Python 알고리즘

Maximum Subarray Sum with Kadane's Algorithm in Python

Find the run of numbers with the largest sum in one pass, even when the list has negative values.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개
배울 내용
  • The best sum ending at each position
  • Starting fresh when the running sum hurts
  • O(n) time and O(1) memory
Python 컴파일러에서 실행 →
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
-2
1
-3
4
-1
2
1
-5
4
4 - 1 + 2 + 1 = 6 is the largest sum of any contiguous run.

Extend the run or start again

최대 부분 배열(maximum subarray) 문제는 양수와 음수가 섞인 리스트에서 합이 가장 큰 연속된 요소 구간을 찾는 문제입니다. 카데인 알고리즘은 현재 위치에서 끝나는 구간의 가장 좋은 합을 기억하면서 이 문제를 아주 효율적으로 풉니다.

핵심 포인트

  1. current = max(value, current + value): keep the run only if it helps.
  2. best = max(best, current) remembers the best run so far.
  3. Start both from the first value so all-negative lists work.

언제 사용하나요?

  • 논리적 사고력을 기르고 알고리즘이 동작하는 과정을 단계별로 이해합니다.
  • 데이터가 많거나 프로그램을 빠르게 만들어야 할 때 알맞은 방법을 고릅니다.
  • 시험, 과제, 코딩 면접을 준비합니다.

예제 코드

코드 실행 →
main.py
def maximum_subarray_sum(values):
    current = best = values[0]
    for value in values[1:]:
        current = max(value, current + value)
        best = max(best, current)
    return best

print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
이 예제의 실행 버튼 만들기

실행 결과

6

코드 설명

각 요소마다 변수 current는 두 가지 중 하나를 고릅니다. 이 요소에서 새 구간을 시작하거나, current + value로 이전 구간을 이어 가는 것입니다. 변수 best는 지금까지 나온 가장 큰 합을 기억합니다. 예제 데이터에서는 [4, -1, 2, 1] 구간이 최대 합 6을 만듭니다. 이 알고리즘은 O(n) 시간에 실행되고 O(1) 메모리만 씁니다.

값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지