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

dp문제이다. 처음 주어진 수열에 펄스 수열을 곱해준 두개의 수열로 나누어서 해당 조건의 최대값을 구하면 된다.
코드의 핵심적인 부분은 이전까지의 합 + 현재값 < 현재값 이면 이면 해당 인덱스의 dp는 현재값으로 넣어준다는 것이다.
예시로 -1 -2 3 -2 4 과 같은 수열에대해 dp는 항상 합의 최대를 저장해주어야하기 때문에 다음과 같이 나온다.

수열 => -1 -2 3 -2 4
dp => -1 -2 3 1 5

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

long long find_max(vector<int> v)
{
    vector<long long> dp(v.size());
    dp[0] = v[0];
    // 이전까지의 합 + 현재값 과 현재값 중 큰것이 dp값이다.
    for(int i=1;i<dp.size();i++) dp[i] = max(1LL*v[i], dp[i-1] + v[i]);
    long long res;
    res = *max_element(dp.begin(), dp.end());// 가장큰 dp값
    return res;
}

long long solution(vector<int> sequence)
{
    vector<int> v1(sequence), v2(sequence);
    for(int i=0;i<sequence.size();i++)
    {
        if (i%2) v1[i] *= -1;
        else v2[i] *= -1;
    }
    return max(find_max(v1), find_max(v2));
}