[알고리즘/C++] 프로그래머스 - 연속 펄스 부분 수열의 합 (Lv.3, DP)

✏️ 풀이 방법
DP를 사용하지 않고 이중 for문을 사용하면 시간초과가 난다.
[DP 사용 방법]
1. i번째 원소까지 더했을때의 최대값을 저장
2. dp[i-1](=이전 인덱스 까지의 최대값) + sequence[i] 의 값과
그냥 sequence[i] 값을 비교해서 최대인 값을 저장한다.

long long solution(vector<int> sequence)
{
    vector<long long> pulsePos(sequence.size());
    vector<long long> pulseNeg(sequence.size());

    for (int i = 0; i < sequence.size(); ++i)
    {
        pulsePos[i] = sequence[i] * ((i % 2 == 0) ? 1 : -1);
        pulseNeg[i] = sequence[i] * ((i % 2 == 0) ? -1 : 1);
    }

    vector<long long> dpPos(sequence.size(), 0);
    vector<long long> dpNeg(sequence.size(), 0);
    dpPos[0] = pulsePos[0];
    dpNeg[0] = pulseNeg[0];

    for (int i = 1; i < sequence.size(); ++i)
    {
        dpPos[i] = max(dpPos[i - 1] + pulsePos[i], (long long)pulsePos[i]);
        dpNeg[i] = max(dpNeg[i - 1] + pulseNeg[i], (long long)pulseNeg[i]);
    }

    long long maxPos = *max_element(dpPos.begin(), dpPos.end());
    long long maxNeg = *max_element(dpNeg.begin(), dpNeg.end());

    return max(maxPos, maxNeg);
}