[Algorithm] Kadane's Algorithm (카데인 알고리즘)
카데인 알고리즘 DP (Dynamic Programming) 기법 중 하나로서, 각 수들을 더했을 때 가장 큰 수가 나오는 연속된 부분을 찾는 알고리즘 ( 시간복잡도: O(n) ) local_max[i] = max (A[i] + local_max[i- 1 ] , A[i]) 많은 분들이 Maximum Subarray Problem 문제 해결방법을 알아보다 카데인 알고리즘을 알게되었을텐데, Maximum Subarray Problem을 통해 카데인 알고리즘을 알아보겠습니다. Maximum Subarray Problem (최대 부분 합 구하기) 최대 부분 합 구하기 문제는 주어진 1차원 배열의 부분 배열에서 최대 합을 가지는 값을 구하는 문제입니다. A = [- 2 , 1 , - 3 , 4 , - 1 , 2 , 1 , - 5 , 4 ] 위 배열에서 가장 큰 합을 가지는 부분 배열은 [4, -1, 2, 1]이며, 최대 합은 6이 됩니다. 저를 포함하여 대다수가 Brute Force로 접근했을텐데 Brute Force를 간단하게 알아보겠습니다. Brute Force 접근 인덱스 0부터 N-1까지 모든 부분 배열의 합을 구한 뒤, 부분 배열의 합 중 가장 큰 값을 찾는 방식 A[0]부터 A[0..1], A[0..2], A[0..N-1]까지 모든 부분 합을 구한다. Sum 배열에 등록된 A[0]의 모든 부분 합 중, 가장 큰 부분 합(local_max)을 구한다. 1,2 를 반복한다. (A[1]부터 A[1..2], A[1..N-1]까지 local_max 구하고, A[2]에서 local_max 구함을 반복) 0부터 N-1까지 구한 local_max[0...N-1]에서 가장 큰 값(global_max)을 구한다. global_max를 리턴 위 방법은 배열의 사이즈가 커지는 만큼 1-2번을 반복해야하는 횟수도 커집니다. ( 시간 복잡도: O(n 2 ) ) 또한 이미 A[i]에서 구했던 값을 A[i+1]에서 다시 구해야하는 문제가 존재합