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

문제 설명

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

풀이

arr = Sequence * Pulse 

배열의 누적 합을 구하면 [1,-1,1,-1,1,...] 의 펄스를 곱한 것과 같고

배열의 누적 차를 구하면 [-1,1,-1,1,...]의 펄스를 곱한 것과 같은 결과를 얻을 수 있습니다.

 

연속되는 숫자의 합 중 최댓값을 찾는 문제이기 때문에, 이전 합이 0이하라면 이전 값을 초기화하고 현재 부터 연속된 값의 합을 구합니다. 

누적 합 계산

 

누적 차 계산

#include <string>
#include <vector>
#include <climits>

using namespace std;

long long lmax(long long a, long long b){
    if(a < b)
        return b;
    return a;
}

long long solution(vector<int> sequence) {

    vector<int> arr;
    for(int i = 0; i < sequence.size(); i++){
        int num = sequence[i];
        if(i % 2 == 1){
            num *= -1;
        }
        arr.push_back(num);
    }
    
    long long answer = LLONG_MIN;
    long long psum = 0;
    
    for(int i = 0; i < arr.size(); i++){
        psum = lmax(psum, 0) + arr[i];
        answer = lmax(answer , psum);
    }
    
    psum = 0;
    for(int i = 0; i < arr.size(); i++){
        psum = lmax(psum, 0) - arr[i];
        answer = lmax(answer , psum);
    }
    
    return answer;
}

 

 

풀이를 참고한 블로그입니다.

https://allmymight.tistory.com/178

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