 |
컴퓨터 과학에서 최대 연속 부분합 문제(maximum subarray problem)은 주어진 일차원 배열에서 그 합이 최대가 되는 연속 부분 배열을 찾는 문제이다. 예를 들어 일차원 배열 {−2, 1, −3, 4, −1, 2, 1, −5, 4}가 주어졌을 때, 그 합이 최대가 되는 연속 부분 배열은 {4, −1, 2, 1}로서, 그 합이 6이 된다.
Kadane 알고리즘은 배열의 원소를 하나씩 스캔해 가며, 각 원소로 끝나는 가장 큰 연속 부분 배열을 찾는 배열이다.