코딩 테스트 - 연속 펄스 부분 수열의 합

연속 펄스 부분 수열의 합

문제 링크 : 연속 펄스 부분 수열의 합

문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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

풀이 방법

• 펄스 부분 수열을 곱해서 연속 부분 수열의 합 중에 가장 큰 값을 찾는 문제이기 때문에, 전체 배열을 펄스 부분 수열 1, -1로 시작하는 값을 각각 곱해서 각각의 경우에서 부분 수열의 합 중 가장 큰 값을 찾는 방식을 통해 풀고자 했다.
• 부분 수열의 합 중 가장 큰 값을 구하는 방법으로는 동적 계획법(DP)을 통해서 가장 큰 값을 구했다.
  -> 해당 문제 풀이 방법은 O(N)의 시간복잡도가 걸릴 것이고, N은 최대 500,000이기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>

using namespace std;

long long solution(vector<int> sequence) {
    long long answer = 0;
    int n = sequence.size();
    
    // 1로 시작하는 펄스 수열 곱하기
    for (int i = 1; i < n; i += 2){
        sequence[i] *= -1;
    }
    
    // 부분 수열의 합 중 가장 큰 값 구하기
    vector<long long> subSequence(n, 0);
    subSequence[0] = sequence[0];
    answer = max(answer, subSequence[0]);
    
    for(int i = 1; i < n; i++){
        subSequence[i] = max((long long)0, subSequence[i - 1]) + sequence[i];
        answer = max(answer, subSequence[i]);
    }
    
    // -1로 시작하는 펄스 수열 곱하기
    for (int i = 0; i < n; i++){
        sequence[i] *= -1;
    }
    
    // 부분 수열의 합 중 가장 큰 값 구하기
    subSequence[0] = sequence[0];
    answer = max(answer, subSequence[0]);
    
    for(int i = 1; i < n; i++){
        subSequence[i] = max((long long)0, subSequence[i - 1]) + sequence[i];
        answer = max(answer, subSequence[i]);
    }
    
    return answer;
}