[알고리즘] Kadane’s(카데인) Algorithm - Array에서 부분합의 최대 찾기

요즘 매일 leetcode daily 문제를 풀고 있다. 생각보다 동기부여가 잘 되어서 너무 좋다! 

오늘은 Dynamic Programming 알고리즘의 일종인 Kadane’s(카데인) Algorithm에 대해 포스팅해보고자 한다. Dynamic programming은 문제를 sub problems로 나누어, sub problem을 그 다음 step의 답을 구하는데에 계속해서 저장해놓고 이용하는 개념이다. 

---

# Kadane's Algorithm? 

일단 이 알고리즘은 숫자 Array가 주어졌을 때, 이 array 내 연속된 subset 원소들의 합 중 가장 max인 값을 반환하는 알고리즘이다. 문제를 예로 들면 이렇다. 

주어진 배열 A를 [1,-2,3,5,-4,2,5] 라고 했을 때
Maximum Subarray는 [3,5,-4,2,5] 이며, 결과값은 부분 배열의 합인 11 이다.

여기서 포인트는 아래와 같다! 

• 연속된 subset을 구해야한다는 것. 예를 들어 [1, 3, 5, 2, 4]의 subset은 [1, 2, 4]가 될 수 없다는 뜻이다. 
• 브루트포스 O(N^2) 복잡도로 탐색하지말고, Dynamic programming을 이용해 O(N) 복잡도로 간단히 탐색할 것. 

---

그렇다면 어떻게 다이나믹 프로그래밍을 이용해 부분 수열의 max 합을 반환할 수 있을까? 아래 그림을 보자. 

아이디어는, "N단계의 부분합은 N-1단계의 부분합이 반영된 결과라는 것" 이다. 즉, 순차적으로 부분합을 구해 N단계에서 이러한 부분합을 이용할 것인지, 이용하지 않고 초기화하고 다시 N단계 원소부터 새로 부분합을 쌓아갈 것인지를 DP 점화식이 판단하도록 하면 된다. 

이를 점화식으로 나타내면 다음과 같다. 

---

 

위 내용을 python 코드로 표현하면 아래와 같이 나타나진다. localsum과 globalsum 변수를 분리해야 함을 유의하자! 안그러면 잘못된 답을 도출하게 된다. 

def kaden(nums) :
  globalsum = nums[0]
  localsum = nums[0]

  for i in nums[1:] : 
    localsum = max(i, i+localsum)     # it must be continuous array !!
    globalsum = max(localsum, globalsum)
    
  return globalsum