연속 펄스 부분 수열의 합

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다.

펄스 수열이란 [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	result
[2, 3, -6, 1, 3, -1, 2, 4]	10

---

문제 해설

 

펄스수열을 생각하지 말고 최대 정수수열값을 계산하도록 하면 된다.

 

펄스 수열을 곱한 정수 수열을 두개 사용해서 값을 도출하면 해결할 수 있다.

---

첫 번째 시도

#include <string>
#include <vector>
#include <queue>

using namespace std;
void MakeToPulse(vector<int>& input, const int StartPulse, int StartNum)
{
    if (StartNum >= input.size()) return;
    input[StartNum] *= StartPulse;
    MakeToPulse(input, -StartPulse, ++StartNum);
}

long long FindToNumber(const vector<int>& Input)
{
    long long answer = -100001;
    long long now = 0;

    for (int i = 0; i < Input.size(); ++i)
    {
        now += Input[i];
        if (answer < now)
            answer = now;

        if (now < 0)
            now = 0;
    }
    return answer;
}

long long solution(vector<int> sequence) 
{
    vector<int> sequenceToPulseM = sequence;
    MakeToPulse(sequenceToPulseM, -1, 0);
    vector<int> sequenceToPulseP = sequence;
    MakeToPulse(sequenceToPulseP, 1, 0);
    
    long long answer1 = FindToNumber(sequenceToPulseM);
    long long answer2 = FindToNumber(sequenceToPulseP);

    return max(answer1, answer2);
}

성공

 

정수수열의 최대값을 찾는 코드를 작성하고, 해당 코드를 사용해서 최대 정수수열울 두개 구한 다음, 가장 큰 값을 return하면 된다.