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

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

 

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000
• sequence의 원소는 정수입니다.

입출력 예

sequence 

[2, 3, -6, 1, 3, -1, 2, 4] 

result

10

입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

 

 

문제풀이

• -1로 시작하는 펄스와 1로 시작하는 펄스를 그대로 곱한다면 2개의 수열이 나온다.
• 동적 계획법(Dynamic Programming, DP) 문제
• long long 의 계산시 1LL의 중요성
• [2, 3, -6, 1, 3, -1, 2, 4] 의 1부터 시작하는 pulse [2, -3, -6, -1, 3, 1, 2, -4]
• [2, 3, -6, 1, 3, -1, 2, 4] 의 1부터 시작하는 pulse [-2, 3, 6, 1, -3, -1, -2, 4]

#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) 
{
	// 1부터 시작하는 수열, -1부터 시작하는 수열의 벡터
    vector<int> pulse1(sequence), pulse2(sequence);
    
    for(int i = 0; i < sequence.size(); i++)
    {
    	// 짝수나 홀수 값만 곱해준다.
        if (i%2) pulse1[i] *= -1;
        else pulse2[i] *= -1;
    }
    
    return max(find_max(pulse1), find_max(pulse2));
}