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

문제

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

풀이

1. 원래 수열에 [1, -1, 1, -1 ...]과 [-1, 1, -1, 1 ...]를 곱한 각각의 수열을 만든다.
2. 두 수열에서 부분합이 최대인 경우를 찾는다.

⚠️ 부분합 찾을 때, 투 포인터 이용하는 줄 알고 관련 문제도 많이 풀어보고 엄청 삽질했는데 DP로 찾아야했던 것..
잊지말자... 투 포인터로 연속하는 수들의 최댓값 구하는 경우는 전부 다 양수여야 한다는 걸!!!
DP 알고리즘 자체는 어렵지 않았는데 너무 투 포인터에 치우쳐 생각해서 못 풀었던 것 같다.

코드

#include <vector>
#include <algorithm>

using namespace std;

long long solution(vector<int> sequence) {
    int N = sequence.size();
    vector<long long> list1(N);
    vector<long long> list2(N);
    vector<long long> dp1(N);
    vector<long long> dp2(N);
    long long ans = 0;
    
    for(int i=0; i<sequence.size(); i++) {
        if(i%2 == 0) {
            list1[i] = sequence[i];
            list2[i] = -1 * sequence[i];
        }
        else {
            list1[i] = -1 * sequence[i];
            list2[i] = sequence[i];
        }
    }
    
    /* DP */
    dp1[0] = list1[0];
    ans = dp1[0]; //list[0]으로 값 넣어주면 N=1일 때, for문 안돌아서 dp값 접근 못함
    
    for(int i=1; i<N; i++) {
        dp1[i] = max(dp1[i-1] + list1[i], list1[i]);
        ans = max(ans, dp1[i]);
    }
    
    dp2[0] = list2[0];
    if (ans < dp2[0])   ans = dp2[0];
    for(int i=1; i<N; i++) {
        dp2[i] = max(dp2[i-1] + list2[i], list2[i]);
        ans = max(ans, dp2[i]);
    }
    
    return ans;
}