# Kadane's Algorithm - **부분 배열의 최대합**을 구하는 문제는 가장 단순한 방법은 $O(N^2)$의 시간이 걸린다. 하지만, Kadane's Algorithm 을 사용하면 $O(N)$의 시간복잡도로 해결할 수 있다. - Dynamic Programming 해결 방법과 마찬가지로 Kadane's Algorithm은 이전에 구해놓은 값을 다시 활용하는 방법을 사용한다. $i$ 번째 배열까지의 최대합을 구하기 위해서는 1) $i-1$ 번째 배열까지의 최대합과 2) $i$ 번째 값 자기 자신 중 어떤 것이 최대합인지 비교하고 둘 중 하나를 선택한다 - 예를 들어, [1, 2, 3, -5] 배열이 있다고 하자. 3번째 아이템까지의 합은 6인데, 4번째 아이템을 포함하면 1 이 되기 때문에 최대합은 여전히 6이다. 반대로, [-3, 5] 배열이 있다고 할 때, 첫번째 아이템까지의 최대합은 -3 이지만, 2번째 아이템까지 포함하면 2번째 아이템만 포함시키는 것이 최대합이기 때문에 그 전까지의 아이템들을 버리고 2번째 아이템인 5부터 시작하고, 최대합은 5가 된다. [Kadane's Algorithm 예시](https://medium.com/@vdongbin/kadanes-algorithm-%EC%B9%B4%EB%8D%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-acbc8c279f29) ![](https://i.imgur.com/1BM5Aih.png) 참고 자료 --- 1. https://medium.com/@vdongbin/kadanes-algorithm-%EC%B9%B4%EB%8D%B0%EC%9D%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-acbc8c279f29