Kadene's algorithm

최대 부분합을 구할 때 O(log n)의 시간 복잡도로 계산할 수 있는 알고리즘이다.

최대 부분합이란 배열의 연속 부분 집합 중 그 합이 가장 큰 것을 의미한다.

예를 들어, [-2, 1, 3, -1, 2, -6, 3, 1]의 배열에서 최대 부분합은 [1, 3, -1, 2]이다.

 

Kadene's algorithm은 특정 index를 포함하는 그것까지의 부분합이 두 가지 방법으로 계산될 수 있음을 이용한 것이다.

1. index - 1 까지의 부분 합이 양수인 경우: 이전 부분 합 + 현재 값
2. index - 1 까지의 부분 합이 음수인 경우: 현재 값.

 

위 예시의 배열로 각 index에서의 부분합을 구해보자. (prev: 이전 부분 합 배열, cur: 현재 부분 합 배열, sum: 현재 부분 합)

[  -2,   1,   3,   -1,   2,   -6,   3,   1 ]

• index = 0
  • prev: []
  • cur: [-2]
  • sum: -2
• index = 1 (case 2)
  • prev: [-2]
  • cur: [1]
  • sum: 1  
• index = 2 (case 1)
  • prev: [1]
  • cur: [1, 3]
  • sum: 4 
• index = 3 (case 1)
  • prev: [1, 3]
  • cur: [1, 3, -1]
  • sum: 3
• index = 4 (case 1)
  • prev: [1, 3, -1]
  • cur: [1, 3, -1, 2]
  • sum: 5 
• index = 5 (case 1)
  • prev: [1, 3, -1, 2]
  • cur: [1, 3, -1, 2, -6]
  • sum: -1 
• index = 6 (case 2)
  • prev: [1, 3, -1, 2, -6]
  • cur: [3]
  • sum: 3
• index = 7 (case1)
  • prev: [3]
  • cur: [3, 1]
  • sum: 4

이제 최대 부분 합은 sum 중 가장 큰 값을 고르면 된다.

따라서 이 경우 최대 부분합은 index = 4 인 경우의 '5'이다.

 

이 과정을 코드로 표현하면 다음과 같다.