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

https://school.programmers.co.kr/learn/courses/30/lessons/161988

프로그래머스

 

 

접근법

1. 부분 수열이니까 누적합을 사용할 것이다.
2. 수열이므로 이분탐색은 절대 아니다.
3. {1, -1, 1, -1,...} 펄스를 사용하나 {-1, 1, -1, 1...} 펄스를 사용하나 누적합 배열의 원소 값은 차이가 없다. (부호만 다르다.)
4. N이 최대 500,000 이므로 투포인터로 합이 최대인 구간을 찾는 것은 불가능하다.
5. 오잉 배열의 최댓값과 최솟값의 차이가 기댓값이랑 같네???

 

정답코드

#include <string>
#include <vector>
#include<algorithm>

using namespace std;
typedef long long ll;
long long solution(vector<int> seq) {
    vector<ll> arr;
    arr.push_back(seq[0]);
    
    for(int i(1);i<seq.size();i++){ // <1>
        if(i%2) arr.push_back(arr[i-1]+(-1)*seq[i]);
        else arr.push_back(arr[i-1]+seq[i]);
    }
    
    ll maxValue=*max_element(arr.begin(),arr.end());
    ll minValue=*min_element(arr.begin(),arr.end());
    
    long long answer = abs(maxValue-minValue); // <2>
    answer=max(abs(maxValue), answer); // <3>
    answer=max(abs(minValue), answer);
    
    return answer;
}

1. 홀수 인덱스일 때 수열에 -1 펄스를 곱하여 누적합 배열을 구한다. 짝수 인덱스에 -1 펄스가 곱해진 누적합은 부호만 다르다. (앞으로 구할 값에 절댓값이 씌워진 이유)
2. 최댓값과 최솟값의 차이를 구한다. 
3. 0번 인덱스부터 더해진 부분수열이 가장 클 경우도 있기 때문에 <3>과 같은 과정을 거친다.

출제 의도는 DP인 것 같다.

이게 왜 맞지? 애드혹?