최대부분합

[Algotithm] Kadane’s Algorithm

오늘은 Kadane’s Algorithm에 대해 공부해봅시다.Kadane’s Algorithm은 Maximum Sum Subarray Problem(최대 부분합 문제)을 해결하는 기법으로 유명하며,Dynamic Programming(DP)의 여러 기법 중 하나입니다.또한 배열의 요소가 정수 범위라고 가정합니다.핵심배열을 순차적으로 순회하면서, 현재까지의 부분합과 최대 부분합을 유지하는 것이 핵심입니다.처음에는 의미를 한 번에 이해하지 못했는데요.아래 그림을 봅시다.위 그림은 [2, 3, -1, -20, 5, 10]의 최대 부분합을 구하는 과정을 시각화한 그림입니다.x축은 Index를, y축은 요소들의 합을 나타냅니다. 배열의 길이만큼의 그래프가 그려집니다. 그래프를 좀 더 자세히 그려봅시다.두 개의 그래..