학교 과제문제를 보고 고군분투하다가 알게 된 알고리즘입니다. 카데인 알고리즘(Kadane's Algorithm)은 주어진 배열 내에서 최대 연속 부분합(Subarray Sum)을 찾는 알고리즘입니다. 이 알고리즘은 동적 프로그래밍의 한 형태로 볼 수 있으며, 간단하면서도 효율적으로 문제를 해결할 수 있습니다. 음수와 양수가 혼합된 배열에서도 최대 연속 부분합을 O(n)의 시간 복잡도로 찾을 수 있습니다. 작동 원리 카데인 알고리즘의 기본 아이디어는 각 단계에서 "현재까지의 최대 부분합"과 "현재 원소를 포함한 최대 부분합"을 비교하는 것입니다. 이를 통해, 각 위치에서 끝나는 최대 부분합을 찾고, 이 중 최댓값을 최종 결과로 사용합니다. 알고리즘 절차 초기화: 최대 부분합(max_sum)과 현재 부분합(..