프로그래머스 연습문제 : 연속 펄스 부분 수열의 합

• 분류: 구간합, 다이나믹 프로그래밍

코드

#include <string>
#include <vector>
#define MAX(a, b) (a>b?a:b)
using namespace std;

long long solution(vector<int> sequence) {
    long long answer = (sequence[0]>0) ? sequence[0] : -sequence[0];
    
    long long plus_seq = sequence[0];
    long long minus_seq = -sequence[0];
    
    for(int i=1 ; i<sequence.size() ; i++) {
        if(i%2 == 0) {
            plus_seq = MAX(plus_seq + sequence[i], sequence[i]);
            minus_seq = MAX(minus_seq - sequence[i], -sequence[i]);
        } else {
            plus_seq = MAX(plus_seq - sequence[i], -sequence[i]);
            minus_seq = MAX(minus_seq + sequence[i], sequence[i]);
        }
        answer = MAX(answer, MAX(plus_seq, minus_seq));
    }
    return answer;
}

코멘트

최대 구간합 문제를 약간 변형한 문제이다.

기존에는 i번째 원소가 오른쪽 끝인 부분수열들 중 최대 구간합 을 구해가는 다이나믹 프로그래밍으로 해결했는데, 지금은 2종류의 펄스 수열이 있으니 2개의 long long 변수를 굴리면 된다.

i를 0부터 n-1까지 굴리면서 plus_seq에는 짝수 인덱스가 +, 홀수 인덱스가 -인 펄스 수열인 경우를 저장하고 minus_seq에는 반대로 홀수 인덱스가 +, 짝수 인덱스가 -인 펄스 수열의 경우를 저장해 간다.

시간 복잡도 O(n), 공간 복잡도 O(1)에 해결할 수 있다.

복습: 최대 구간합

i번째 원소가 오른쪽 끝인 부분수열들의 최대 구간합은

1. i-1번째 원소가 오른쪽 끝인 부분수열 중 구간합이 최대인 것에 i번째 원소도 이어붙인 부분수열의 합
2. i번째 원소 혼자인 부분수열의 합

두 개 중에서 더 큰 값이 된다. 좀만 생각해 보면 자명