프로그래머스 Level 3 연속펄스부분수열의합

연속펄스부분수열의합 (프로그래머스 Level 3)

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

dp를 사용할 수 있겠다고 생각하여
2차원 dp를 사용하여
dp[i][j] : i부터 j 까지의 ‘수열의 합’을 저장하였으나
O(n^2) 로 인하여 시간 초과가 되어 버렸다

결국 돌고 돌다 검색을 해보니
(https://howudong.tistory.com/210)

1. 특정한 ‘연속 펄스 배열’은 결국 2가지로 나뉘며,
   (1,-1,1,-1,…), (-1,1,-1,1,…)
   이 2 배열을 주어지는 배열에 곱해줌으로서
   ‘펄스’가 적용된 2개의 배열을 만들어 줄 수 있다
   
2. 특정 시점에서 ‘펄스’ 부분합에 대한 값을 비교하여
   dp[i] : i 인덱스까지의 펄스 부분합 중 가장 큰 값
   (추가적으로 뒤집힌 펄스 배열에 대한 내용도 dp2로 저장)
   dp[i] = max(dp[i-1] + i번째 요소, i번째 요소)
   로 잡을 수 있다
   (펄스는 반드시 ‘-‘요소가 포함되며,
   그렇기에 ‘이전’까지의 합이 새로운 요소보다 못하다면
   새로이 시작하는 것이 값이 더 크게 된다)
   
3. 이것을 2개의 펄스 벡터에 대하여 구해줌으로서 구할 수 있다
   

Code

#include <string>
#include <vector>
#include<math.h>
#include<limits.h>

using namespace std;

// 펄스를 곱해준 배열을 생성
vector<int> purse(vector<int> v, int num) 
{
	for (int i = 0; i < v.size(); i++) 
	{
		v[i] = v[i] * num;
		num *= -1;
	}
	return v;
}

long long solution(vector<int> sequence) {
    const size_t sSize = sequence.size();
    long long answer = LONG_MIN;

    if (sSize == 1) 
    {
        answer = abs(sequence[0]);
        return answer;
    }

    // 1로 시작하는 펄스 벡터
    vector<int> seq1 = purse(sequence, 1);
    // -1로 시작하는 펄스 벡터
    vector<int> seq2 = purse(sequence, -1);

    vector<long long> dp1(sSize); // 1 dp 배열
    vector<long long> dp2(sSize);// -1 dp 배열

    dp1[0] = seq1[0];
    dp2[0] = seq2[0];

    for (int i = 1; i < sSize; i++)
    {
        // 이전까지 더한 합이 그냥 지금 새로 시작하는 것보다 못하면 버리고 새로 시작
        dp1[i] = max(dp1[i - 1] + (long long)seq1[i], (long long)seq1[i]);
        answer = max(answer, dp1[i]);
    }

    for (int i = 1; i < sSize; i++) 
    {
        // 이전까지 더한 합이 그냥 지금 새로 시작하는 것보다 못하면 버리고 새로 시작
        dp2[i] = max(dp2[i - 1] + (long long)seq2[i], (long long)seq2[i]);
        answer = max(answer, dp2[i]);
    }

    return answer;
}