Kadane's Algorithm

소개 1차원 배열이 주어졌을 때, 연속된 구간의 최대 합을 구하는 알고리즘을 카데인 알고리즘이라고 한다. 예를 들어 다음 배열이 있다면, [-2, 1, -3, 4, -1, 2, 1, -5, 4] 연속된 구간 [4, -1, 2, 1]의 합인 6이 가장 크다. 카데인 알고리즘은 앞에서 계산한 결과를 재활용하여 배열을 한 번만 순회한다. 따라서 시간 복잡도 O(n), 공간 복잡도 O(1)로 문제를 해결할 수 있다. 아이디어 현재 원소에서 끝나는 연속 구간의 최대 합을 유지하고 다음 원소를 만났을 때 기존 구간을 이어가는 것과 현재 원소부터 새로운 구간을 시작하는 것 중 더 큰 값을 선택한다. ...