[컴][알고리즘] 카데인 알고리즘, Kadane’s Algorithm

 

dp / dynamic programming / Kadane’s Algorithm

카데인 알고리즘

ref.1 에서 자세한 설명을 확인하자.

이 알고리즘은 주어진 list 에서 연속된 element의 최대합을 구할 때 사용한다.

index ’i’까지의 연속된 element의 합들중에 최대값을 local_max 라고 하자.(ref. 1 에서 인용)
이 때 local_max[i] 는 local_max[i-1] 에서 현재 i 의 값 array[i] 를 더한 값이 된다.

그러면 아래처럼 공식이 된다. ref.1 에 보면 그림으로 잘 설명되어 있다.

local_max[1] = max(array[1], local_max[0])

현재 index 까지의 최대값을 구하는 법:

1. traversing 을 하면서 계속 더하면서 max 를 찾는다.

2. 여기서 단한가지, 더하지 않고, 그 ’i번째 값’이 더 클 수 있다.(이전까지의 최대값이 ’음수’일수도 있으니)

   위의 이야기가 아래 공식이다. 그림은 ref. 1 을 참고하자.

   local_max[i] = max(array[i], local_max[i-1])

   이제, 각 index i 에서의 local_max 는 구할 수 있다. 이제 이 local_max 들중 max 를 구하면 된다.

code

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        currmax = nums[0]
        gmax = nums[0]
        
        for i in range(1, len(nums)):
            
            currmax = max(nums[i], currmax + nums[i]) 
            gmax = max(gmax, currmax)
            
            
        return gmax

Reference

1. Kadane’s Algorithm — (Dynamic Programming) — How and Why does it Work? | by Rohit Singhal | Medium
2. Maximum Subarray - LeetCode