[DAY95] Algorithm : Pulse Subsequence

수열에 [1, -1, ...] 또는 [-1, 1, ...] 패턴을 곱했을 때 나올 수 있는 연속 부분 수열의 합 중 최댓값을 구하는 문제다. 부분 수열의 합을 구하는 가장 빠른 방법인 카데인 알고리즘(Kadane's Algorithm)을 두 가지 펄스 패턴에 동시에 적용하여 $O(N)$으로 해결한다.

---

❓ 문제 분석

• 목표: 펄스 수열을 곱한 뒤, 연속된 부분 수열의 합 중 최댓값(max) 찾기.
• 제약 조건:
  • 수열 길이: 최대 500,000 / 원소 값: $\pm$ 100,000
  • 최악의 경우 합계가 500억을 넘을 수 있으므로 long long 자료형이 필수다.
  • 시간 복잡도는 $O(N)$ 혹은 $O(N \log N)$이어야 한다. ($O(N^2)$은 시간 초과)
• 핵심 키워드: "연속 부분 수열", "펄스(1, -1 반복)", "최댓값"

---

💡 풀이 설계

1. 시도했던 접근 (Observation)

• 펄스 수열은 [1, -1, 1, ...]과 [-1, 1, -1, ...] 두 가지 경우밖에 없다.
• 각 경우에 대해 수열을 변환한 뒤, "연속된 수들의 합 중 최댓값"을 구하면 된다.

2. 최종 해결책 (Kadane's Algorithm)

• 전략: 연속 부분 수열의 합을 $O(N)$만에 구하는 카데인 알고리즘을 사용한다.
• 핵심 로직:
  1. 반복문을 돌며 현재 원소(sequence[i])에 두 가지 펄스 패턴을 각각 적용한다.
     • 패턴 1: sequence[i] * (-1)^i
     • 패턴 2: sequence[i] * (-1)^(i+1)
  2. 각 패턴별로 누적합(current_sum)을 더해나간다.
  3. Reset: 만약 누적합이 음수가 되면, 그 부분은 버리고 0부터 다시 시작한다. (음수를 더하고 가는 것보다 새로 시작하는 게 이득이기 때문)
  4. 매번 total_max를 갱신한다.

---

💻 코드 구현

#include <vector>
#include <algorithm>

long long solution(std::vector<int> sequence) {
    long long total_max = 0;
    long long current_sum1 = 0; // 패턴 1용 누적합
    long long current_sum2 = 0; // 패턴 2용 누적합

    for (int i = 0; i < sequence.size(); ++i) {
        long long val1, val2;

        // 인덱스가 짝수일 때와 홀수일 때를 나누어 패턴 각각 적용
        if (i % 2 == 0) {
            val1 = (long long)sequence[i];      // 패턴 1: 1 곱하기
            val2 = (long long)sequence[i] * -1; // 패턴 2: -1 곱하기
        } else {
            val1 = (long long)sequence[i] * -1; // 패턴 1: -1 곱하기
            val2 = (long long)sequence[i];      // 패턴 2: 1 곱하기
        }

        // 카데인 알고리즘: 누적합이 0보다 작아지면 버리고 0부터 다시 시작
        current_sum1 = current_sum1 + val1;
        if (current_sum1 < 0) {
            current_sum1 = 0;
        }

        current_sum2 = current_sum2 + val2;
        if (current_sum2 < 0) {
            current_sum2 = 0;
        }

        // 전체 최댓값 갱신
        if (current_sum1 > total_max) {
            total_max = current_sum1;
        }
        if (current_sum2 > total_max) {
            total_max = current_sum2;
        }
    }

    return total_max;
}

---

🐛 시행착오 및 디버깅

• 자료형: 입력값이 최대 10만, 길이가 50만이므로 합계가 int 범위를 초과할 수 있다. 모든 누적 변수를 long long으로 선언하여 오버플로우를 방지했다.
• 초기화: total_max를 0으로 초기화했을 때 모든 값이 음수라면 문제가 될 수 있다. 하지만 펄스 수열은 원소의 부호를 뒤집기 때문에, 적어도 하나의 원소는 양수(또는 0)가 되므로 0으로 초기화해도 정답을 구할 수 있다.

---

✅ 오늘의 회고

항목	내용
유형	다이나믹 프로그래밍 (DP), 카데인 알고리즘
체감 난이도	중 (카데인 알고리즘을 모르면 어려움)
복잡도	시간: $O(N)$, 공간: $O(1)$
새로 배운 것	카데인 알고리즘의 핵심 아이디어("누적합이 음수면 버린다")를 활용하여 연속 부분 수열의 최댓값을 효율적으로 구하는 법을 익혔다.