프로그래머스 - 연속 펄스 부분 수열의 합 [C++]

 이 문제는 다이나믹 프로그래밍을 이용해서 풀었다. 일단 sequence 의 최대 길이가 500,000이므로 O(n) 이하의 알고리즘을 사용해야만 시간 안에 풀 수 있다. 부분 수열마다 펄스 배열을 곱해서 그 최대를 구하라는 문제였지만, 사실 각 숫자마다 1 아니면 -1이 무조건 곱해지게 된다. 따라서 -1을 처음에 곱한 배열과 1을 처음에 곱한 배열 두개에 대해 다이나믹 프로그래밍으로 풀면 정답이 나오게 된다.

 

 

 나는 1, -1로 시작한 배열 두개에 대한 O(n) 알고리즘을 통해 풀 수 있다는 사실까지는 알아냈지만, 최댓값을 알아내는 알고리즘을 생각해내지 못했다. 처음에는 투 포인터를 생각했지만, 정렬이 되어있지 않은 배열 특성상 알아내기 어려웠다. 그래서 검색을 통해 다이나믹 프로그래밍을 이용하면 된다는 사실을 알아내어 문제를 풀었다. 다이나믹 프로그래밍을 떠올리기만 했다면 풀 수 있는 문제였는데 아쉬웠다.

 

 

 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long dp1[500000];
long long dp2[500000];

long long solution(vector<int> sequence) {
    long long answer = -50000000000;
    
    vector<long long> seq1;
    vector<long long> seq2;
    
    int start = 1;
    for (int s : sequence) {
        seq1.push_back(s * start);
        seq2.push_back(s * start * -1);
        start *= -1;
    }
    
    dp1[0] = seq1[0];
    dp2[0] = seq2[0];
    
    for (int i = 1; i < sequence.size(); i++) {
        dp1[i] = max(dp1[i - 1] + seq1[i], seq1[i]);
        dp2[i] = max(dp2[i - 1] + seq2[i], seq2[i]);
    }
    
    for (int i = 0; i < sequence.size(); i++) {
        answer = max(answer, max(dp1[i], dp2[i]));
    }
    
    return answer;
}