[Programmers] 연속 펄스 부분 수열의 합(Lv.3)

풀이 소요시간 : 실패(60분 초과)

우선 아래 코드는 주어진 일차원 배열에서 최대 구간합을 구하는 DP 알고리즘이다.

int dynamic_programming(vector<int> arr){
    int result = INT_MIN;
    int size = arr.size();
    vector<int> dp(size);

    for (int i=0;i<size;i++){
        if (dp[i-1] + arr[i] > arr[i]) dp[i] = dp[i-1] + arr[i];
        else dp[i] = arr[i];
    }

    for (int i=0;i<size;i++){
        result = max(result, dp[i]);
    }

    return result;
}

처음에 DP 로 접근하려다가 투 포인터 로 접근을 바꿨다가 풀이 방식이 너무 괴랄해서 한참을 고생했다. 위의 구간합 알고리즘은 바이블로 삼아야 할 정도로 깔끔하다. 배열에 0, 양수, 음수 가 모두 포함되어도 작동하는 기가막힌 동적 계획법이다. 안타깝게도 스스로 발상하지는 못했지만, 기억해놓고 다음에 꼭 써먹자.

전체 코드

long long 타입이 주로 등장하는 DP 유형의 문제는 타입캐스팅을 항상 조심해야한다.
max 메소드의 두 매개변수의 자료형이 같아야 작동하는 것은 이번에 처음 알았다.
sequence[0] 부터 MAX 값을 적용하기 위해서는 세심하게 신경써야 할 부분도 있었다.

#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

long long N;
long long DP[500000][2];

long long solution(vector<int> sequence) {
    
    N = sequence.size();
    vector<long long> V1(N, 0);
    vector<long long> V2(N, 0);
    long long P1 = 1;
    long long P2 = -1;
    
    for(int i = 0; i < N; i++) 
    {
        V1[i] = (long long)(sequence[i] * P1);
        V2[i] = (long long)(sequence[i] * P2);
        P1 *= -1;
        P2 *= -1;
    }
    //각 수열이 완성됨 -> 각 수열의 가장 큰 연속 부분수열의 합을 구하면 된다.
    //두 수열의 Max 를 비교하여 가장 큰 Max 를 선정하면 됨
    
    
    
    
    DP[0][0] = max((long long)0, V1[0]);
    DP[0][1] = max((long long)0, V2[0]);
    
    long long Max_1 = DP[0][0];
    long long Max_2 = DP[0][1];
    
    for(int i = 1; i < N; i++)
    {
        DP[i][0] = max(DP[i - 1][0] + V1[i], V1[i]);
        Max_1 = max(Max_1, DP[i][0]);
        
        DP[i][1] = max(DP[i - 1][1] + V2[i], V2[i]);
        Max_2 = max(Max_2, DP[i][1]);
    }
    
    return max(Max_1, Max_2);
    
}