백준 1912번 [연속합](C++) -yes6686- 티스토리

백준 문제 풀이: 1912 [연속합]

---

문제 링크: https://www.acmicpc.net/problem/1912

문제 설명:

N개의 정수로 이루어진 배열에서 연속된 부분 배열의 합이 최대가 되는 값을 구하는 문제입니다. 모든 수가 음수인 경우도 고려해야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[100001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int isAllNegative = 1;
    int maxAns = -1001;

    // 입력값 처리 및 초기 최대값 계산
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        if (arr[i] > 0) isAllNegative = 0; // 양수가 존재하는지 체크
        if (maxAns < arr[i]) {
            maxAns = arr[i];
        }
    }

    // 모든 수가 음수인 경우 최대값을 출력
    if (isAllNegative == 1) {
        cout << maxAns << '\n';
        return 0;
    }

    int sumGoing = 0;
    for (int i = 0; i < n; i++) {
        sumGoing += arr[i]; // 현재 값을 누적합에 추가
        if (sumGoing < 0) {
            sumGoing = 0; // 누적합이 음수가 되면 초기화
        }
        maxAns = max(maxAns, sumGoing); // 최대값 갱신
    }

    cout << maxAns << '\n';
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 카데인 알고리즘(Kadane's Algorithm)을 사용하여 최대 연속 부분 배열 합을 계산합니다.
• 구현 세부사항:
  • 음수만 존재하는 경우를 처리하기 위해 배열의 최대값을 별도로 저장
  • 양수가 존재하면 누적합(sumGoing)을 계산하며 음수일 경우 초기화
  • 누적합을 계산하면서 최대값을 갱신
• 시간 복잡도: O(n)
  • 배열을 한 번 순회하며 최대값을 계산

---

결과

주어진 배열에서 연속된 부분 배열의 최대 합을 효율적으로 계산합니다. 카데인 알고리즘을 활용해 O(n)의 시간 복잡도로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!