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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

문제풀이

투 포인터로 풀어봤는데 테스트 케이스 몇 개에서 시간 초과가 떴다

질문글을 봤더니 DP로 풀 수 있어서 다시 작성했다.

DP[idx][0]에는 항상 최댓값을, DP[idx][1]에는 항상 최솟값을 저장한다.

(DP[idx][0]는 DP[idx-1][0] + seq[idx], DP[idx-1][1] + seq[idx], seq[idx] 중 최댓값)

(DP[idx][0]는 DP[idx-1][0] + seq[idx], DP[idx-1][1] + seq[idx], seq[idx] 중 최솟값)

answer에는 DP[idx][0]와 DP[idx][1] 중 절댓값이 큰 값을 저장한다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

long long solution(vector<int> sequence) {
    long long answer(0), idx(0);
    vector<vector<long long>>DP(sequence.size(), vector<long long>(2, 0));

    DP[0] = { sequence[0], 0 };
    answer = abs(sequence[0]);
    for (idx = 1; idx < sequence.size(); ++idx) {
        if (idx % 2 == 0) {
            DP[idx][0] = sequence[idx] + max(DP[idx - 1][0], max(DP[idx - 1][1], (long long)0));
            DP[idx][1] = sequence[idx] + min(DP[idx - 1][0], min(DP[idx - 1][1], (long long)0));
        }
        else if (idx % 2 == 1) {
            DP[idx][0] = sequence[idx] * -1 + max(DP[idx - 1][0], max(DP[idx - 1][1], (long long)0));
            DP[idx][1] = sequence[idx] * -1 + min(DP[idx - 1][0], min(DP[idx - 1][1], (long long)0));
        }
        answer = max(answer, max(abs(DP[idx][0]), abs(DP[idx][1])));
    }

    return answer;
}