카데인 알고리즘 (Kadane's Algorithm) ?배열 내의 연속된 부분 배열의 합 중에서 합이 최대인 부분 배열을 찾는 알고리즘이다.배열을 한 번 순회하면서 현재 위치에서 끝나는 가장 큰 부분 배열의 합을 계산하고 이를 통해 전체 배열에서의 최대 부분 배열 합을 구하는 방식이다. 이 알고리즘은 시간 복잡도가 O(n), 공간 복잡도가 O(1)로 매우 효율적이다. 또한 1차원 배열뿐만 아니라 2차원 배열에서도 적용할 수 있다. 2차원 배열에서 최대 합을 갖는 부분 행렬을 찾는 문제는 복잡하지만 알고리즘을 행별로 적용하여 문제를 1차원 문제로 축소함으로써 해결할 수 있다. 핵심 아이디어카데인 알고리즘은 다음과 같은 두 가지 값을 사용한다.현재까지의 최대 부분 배열 합 (current_max) : 특정 ..