알고리즘: 카데인 알고리즘 (Kadane's algorithm)

이 알고리즘은 배열에서 연속된 부분 배열의 구간 합 중 가장 큰 값을 찾는 알고리즘이다.

보통 배열에서 최대 연속 구간합을 찾을 때에는 정렬 후 투포인터를 사용하게 되는데,

위 알고리즘은 정렬할 수 없는 경우에 유용하게 사용할 수 있다.

시간 복잡도는 O(n)이다.

카데인 알고리즘의 기본 아이디어

1. 현재부분합, 최대부분합 두개의 변수를 사용한다.
2. 배열의 각 요소를 순회하면서 현재까지의 최대 부분합을 추적한다.
3. 현재 요소를 포함하는 것이 유리한지, 아니면 새로운 부분 배열을 시작하는 것이 더 유리한지를 비교하여 현재 부분합을 업데이트한다.
4. 전체 배열을 순회하면서 최대 부분합을 갱신합니다.

카데인 알고리즘 구현 (C++)

#include <iostream>
#include <vector>
#include <algorithm> // std::max

int maxSubArraySum(const std::vector<int>& nums) {
    // 초기값 설정
    int currentSum = nums[0];  // 현재까지의 최대 부분합
    int maxSum = nums[0];      // 전체에서의 최대 부분합

    // 두 번째 요소부터 배열 끝까지 순회
    for (size_t i = 1; i < nums.size(); ++i) {
        // 현재 요소를 포함한 부분합 vs 현재 요소 자체를 비교
        currentSum = std::max(nums[i], currentSum + nums[i]);

        // 최대 부분합을 갱신
        maxSum = std::max(maxSum, currentSum);
    }

    return maxSum;
}

int main() {
    std::vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    
    // 최대 부분합 출력
    std::cout << "최대 부분합: " << maxSubArraySum(nums) << std::endl;

    return 0;
}

코드 설명

1. 초기값 설정:
   • currentSum과 maxSum을 배열의 첫 번째 요소로 초기화한다.
2. 배열 순회:
   • 두 번째 요소부터 순회하면서 currentSum을 계산한다.
   • 현재 요소를 포함한 값(currentSum + nums[i])과 현재 요소(nums[i]) 중 더 큰 값을 currentSum에 저장한다.
3. 최대 부분합 갱신:
   • maxSum을 currentSum과 비교하여 더 큰 값을 저장합니다.
4. 최종 결과 반환:
   • maxSum에 최대 부분합이 저장된다.

실행 예시

주어진 배열이 {-2, 1, -3, 4, -1, 2, 1, -5, 4}일 때, 최대 부분합은 6이며, 이는 배열의 [4, -1, 2, 1] 구간의 합이다.

시간 복잡도

• 이 알고리즘은 배열을 한 번 순회하면서 계산을 수행하므로 시간 복잡도는 O(n)이다.