카데인 알고리즘(kadne`s Algorithm) 연속된 부분 배열 중 최대 합 찾기

카데인 알고리즘

배열 내 연속된 부분 배열(subarray) 중에서  가장 최대 합을 찾는 알고리즘이다. 

• DP(Dynamci Programming)를 적용한 방식
• 완탐시 O(N^2) 걸리는 거를 O(N)으로!

핵심은 각각의 최대 부분합은 이전 최대 부분합이 반영된 결과값이다. 
MAX(자기 자신 , 바로 이전의 부분합)

 

 

파이썬 코드 및 예제

def maxSubArray(nums):
    max_current = max_global = nums[0]

    for i in range(1, len(nums)):
        max_current = max(nums[i], max_current + nums[i])
        max_global = max(max_global, max_current)
    
    return max_global

 

nums = `[-2,1,-3,4-1,2,1,-5,4]` 일 때 부분합의 최대합은 6

i	nums[i]	max_current	max_global	max_global
0	-2	-2	-2	-2
1	1	max(1, -2+1) = 1	max(-2,1) = 1	1
2	-3	max(-3, 1-3) = -2	max(1, -2) = 1	1
3	4	max(4, -2+4) = 4	max(1, 4) = 4	4
4	-1	max(-1, 4-1) = 3	max(4, 3) = 4	4
5	2	max(2, 3+2) = 5	max(4, 5) = 5	5
6	1	max(1, 5+1) = 6	max(5,6) = 6	6
7	-5	max(-5, 6-5) = 1	max(6,1) = 6	6
8	4	max(4, 1+4) = 5	max(6,5) =6	6

 

 

• 카데인 알고리즘의 장점 시간 효율성: 배열을 한 번만 순회하므로 시간 복잡도가 O(n)으로, 매우 큰 배열에서도 효율적
• 동적 프로그래밍을 사용하여 배열의 각 요소에서 가능한 최대 값을 동적으로 구할 수 있어 코드가 간결
• 카데인 알고리즘은 연속된 부분 배열의 합 문제를 해결할 때 매우 유용하며, 다양한 변형 문제에도 응용될 수 있습니다.

 

 

그림 출처 : https://medium.com/@vdongbin/kadanes-algorithm-%EC%B9%B4%EB%8D%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-acbc8c279f29