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

펄스 수열은 두 종류가 있다

[-1, 1, -1...] , [1, -1, 1...]

sequence가 주어지면 -1로 시작하는 펄스 수열과 곱해진 s1배열,

1로 시작하는 펄스 수열과 곱해진 s2배열 두가지로 나누어 생각했다.

 

가장 쉽게 생각할 수 있는 풀이방법은

DFS로 모든 경우의 수를 탐색하는 방법이었다.

(하지만 이 방법은 시간 초과이다.)

 

다음으로 생각해본 방법은 DP이다.

 모든 경우의 수를 탐색하면 이미 더했던 부분수열을

다시 더하고 하는 중복과정이 계속 발생한다.

또한 부분수열은 연속해서 이어지는 일렬의 과정이므로

for문 한번으로 해결할 수 있을 것 같았다.

 

입출력예제 cn1 결과

과정은 s1과 s2를 나누어서 계산을 했다.

cnt1과 cnt2는 dp배열로,

i번째 위치의 의미는 해당 위치에서 나올 수 있는 부분수열의 합 중 가장 최대값을 의미한다.

ex) cnt1[3]은 [-2, 3, 6, 1]에서 부분수열의 합 중 가장 최대값인 3+6+1 = 10을 값으로 가진다.

 

초기 0번째 값은 각 배열의 0번째 인덱스 값이다.

 

이후 1번째 인덱스부터 dp값을 채워가는데,

i-1의 dp값이 음수이면 더해도 합이 최대가 될 수 없으니,

i-1대신 0을 선택한다.

 max((long long)0, cnt1[i-1]) + s1[i];

 

DP를 채워나가면서 합이 최대인 answer의 값을 구한다.

 

-100,000 ≤ sequence의 원소 ≤ 100,000 이므로 dp값을 저장할 cnt1, cnt2는 long long배열이어야 한다.

16 18 19 20에서 실패가 떠서 고민해보니 자료형을 잘못 썼다!

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

using namespace std;

long long solution(vector<int> sequence) {
    long long answer = -200000;
    int len = sequence.size();
    int s1[len], s2[len];
    for(int i=0; i<len; i++){
        s1[i] = i%2 ? sequence[i] : -sequence[i];
        s2[i] = i%2 ? -sequence[i] : sequence[i];
    }
    
    long long cnt1[len], cnt2[len];
    cnt1[0] = s1[0];
    cnt2[0] = s2[0];
    answer = max(cnt1[0], cnt2[0]);
    for(int i=1; i<len; i++){
        cnt1[i] = max((long long)0, cnt1[i-1]) + s1[i];
        cnt2[i] = max((long long)0, cnt2[i-1]) + s2[i];
        
        if(answer < cnt1[i])
            answer = cnt1[i];
        if(answer < cnt2[i])
            answer = cnt2[i];
    }
    return answer;
}

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