최대 부분 배열 합 (Maximum Subarray Sum)

최대 부분 배열 합(Maximum Subarray Sum) 문제는 주어진 배열에서 연속된 부분 배열 중에서 가장 큰 합을 갖는 부분 배열을 찾는 문제이다. 이 문제는 배열에서 연속된 요소들의 합을 최대화하는 부분 배열을 찾는 것이 목표이다.

문제 정의

• 주어진 배열에서 연속된 부분 배열의 합이 최대가 되는 부분 배열을 찾는다.
• 배열의 원소는 양수와 음수 모두 포함될 수 있다.
• 예를 들어, 배열 [-2, 1, -3, 4, -1, 2, 1, -5, 4]가 주어진다면, 최대 부분 배열 합은 6이며, 그 부분 배열은 [4, -1, 2, 1]입니다.

 

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

이 문제는 카데인 알고리즘(Kadane’s Algorithm)을 사용하여 O(n)의 시간 복잡도로 해결할 수 있다. 카데인 알고리즘은 현재까지의 최대 부분 배열의 합을 유지하면서, 배열을 한 번만 순회하여 최적의 해를 찾는 방법이다.

카데인 알고리즘의 핵심 아이디어:

1. 현재까지의 최대 합을 유지하면서 배열을 한 번 순회한다.
2. 각 단계에서 현재 요소를 포함한 부분 배열을 만들 때, 그 이전까지의 최대 부분 배열 합에 현재 요소를 더한 값과, 현재 요소 그 자체를 비교한다.
3. 두 값 중 더 큰 값을 현재 최대 부분 배열의 합으로 선택한다.
   • 즉, 이전까지의 최대 부분 배열 합에 현재 값을 더했을 때 더 커진다면, 이를 계속 이어가고,
   • 현재 값이 더 크다면, 새로운 부분 배열을 시작하는 것으로 간주한다.
4. 모든 요소를 탐색한 후, 가장 큰 값이 최대 부분 배열 합이 된다.

점화식:

• max_current: 현재까지의 부분 배열의 최대 합 (지금까지 본 값 중에서 최대 합).
  • max_current = max(arr[i], max_current + arr[i])
    • 현재 요소와, 그 요소를 이전 최대 합에 더한 값 중 더 큰 값을 선택한다.
• max_global: 지금까지의 전체 배열에서의 최대 부분 배열의 합.
  • max_global = max(max_global, max_current)

카데인 알고리즘 구현

def max_subarray_sum(arr):
    # 첫 번째 요소로 초기화
    max_cur = max_global = arr[0]

    # 배열의 두 번째 요소부터 시작해서 순회
    for i in range(1, len(arr)):
        # 현재 요소를 포함한 부분 배열의 최대 합을 계산
        max_cur = max(arr[i], max_cur + arr[i])

        # 전체 최대 합을 업데이트
        if max_cur > max_global:
            max_global = max_cur

    return max_global

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(arr))  # 6

코드 설명:

1. 초기화: 배열의 첫 번째 요소를 max_current와 max_global로 초기화한다. 처음에는 첫 번째 요소가 가장 큰 부분 배열의 합일 수 있으므로 이 값으로 시작한다.
2. 루프를 통해 배열 순회:
   • 각 단계에서 현재 요소를 포함한 부분 배열을 만들고, 그 부분 배열의 합을 max_current로 저장한다.
   • 이전 부분 배열에 현재 요소를 더한 값(max_current + arr[i])과 현재 요소 그 자체(arr[i])를 비교하여, 더 큰 값을 선택한다.
3. 최대 합 업데이트: max_current가 max_global보다 크다면, 이를 갱신하여 지금까지 탐색한 부분에서 가장 큰 부분 배열 합을 유지한다.
4. 결과 반환: max_global에는 최대 부분 배열 합이 저장되며, 이 값을 반환한다.

 

예시

배열: [-2, 1, -3, 4, -1, 2, 1, -5, 4]

이 배열에 대해 카데인 알고리즘을 적용하면:

1. 초기값:
   • max_current = -2, max_global = -2 (첫 번째 값으로 초기화)
2. 두 번째 요소 1:
   • max_current = max(1, -2 + 1) = 1
   • max_global = max(-2, 1) = 1
3. 세 번째 요소 3:
   • max_current = max(-3, 1 + -3) = -2
   • max_global = max(1, -2) = 1
4. 네 번째 요소 4:
   • max_current = max(4, -2 + 4) = 4
   • max_global = max(1, 4) = 4
5. 다섯 번째 요소 1:
   • max_current = max(-1, 4 + -1) = 3
   • max_global = max(4, 3) = 4
6. 여섯 번째 요소 2:
   • max_current = max(2, 3 + 2) = 5
   • max_global = max(4, 5) = 5
7. 일곱 번째 요소 1:
   • max_current = max(1, 5 + 1) = 6
   • max_global = max(5, 6) = 6
8. 여덟 번째 요소 5:
   • max_current = max(-5, 6 + -5) = 1
   • max_global = max(6, 1) = 6
9. 아홉 번째 요소 4:
   • max_current = max(4, 1 + 4) = 5
   • max_global = max(6, 5) = 6

최종적으로 최대 부분 배열 합은 6이며, 그 부분 배열은 [4, -1, 2, 1]이다.

 

시간 복잡도

카데인 알고리즘은 배열을 한 번만 순회하면서 연속된 부분 배열의 합을 구한다.

• 시간 복잡도: O(n)

→ 배열을 한 번만 순회하므로, n개의 원소에 대해 각각 상수 시간 작업을 수행한다.

• 공간 복잡도: O(1)

→ 추가 메모리를 거의 사용하지 않고, 단일 변수(max_current, max_global)만 유지한다.

 

동적 프로그래밍과의 관계

카데인 알고리즘은 본질적으로 동적 프로그래밍(Dynamic Programming) 기법의 한 예이다. 이 알고리즘은 다음과 같은 동적 프로그래밍의 핵심 개념을 사용한다:

1. 최적 부분 구조 (Optimal Substructure): 현재 단계에서의 최적 해가 그 이전 단계의 최적 해를 바탕으로 결정된다.
2. 중복되는 하위 문제: 각 단계에서 이전 단계의 결과를 사용하여 다음 단계의 결과를 계산한다.

최대 부분 배열 합 문제의 확장

1. 2차원 배열에서의 최대 부분 배열 합:
   • 문제를 2차원 배열로 확장할 수도 있다. 이 경우에는 1차원 카데인 알고리즘을 각 행 또는 열을 대상으로 적용하여 해결할 수 있다.
2. 최대 부분 곱 배열(Maximum Product Subarray):
   • 최대 곱을 찾는 문제도 유사한 방식으로 해결할 수 있지만, 곱셈의 경우 음수와 양수의 특성 때문에 더 복잡해진다. 이 경우에는 최대 곱과 최소 곱을 함께 추적해야 한다.

 

• 최대 부분 배열 합(Maximum Subarray Sum) 문제는 주어진 배열에서 연속된 부분 배열 중에서 합이 최대가 되는 부분 배열을 찾는 문제이다.
• 카데인 알고리즘(Kadane's Algorithm)은 O(n) 시간 복잡도로 문제를 해결할 수 있다. 이 알고리즘은 현재까지의 최대 합을 유지하며, 배열을 한 번만 순회하여 최적의 해를 찾는다.
• 카데인 알고리즘은 동적 프로그래밍의 최적 부분 구조와 중복되는 하위 문제 개념을 활용한 효율적인 알고리즘이다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms