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

연속 펄스 부분 수열의 합 ←클릭

누적 합 이외에 dp를 사용한 문제 풀이이다.

누적합을 사용한 풀이 ←클릭

변수 설정

new1: 이전 dp배열과 현재 sequence배열의 합이다.
dp: dp배열 i번째 인덱스까지 최선의 연속 펄스 부분 수열의 합
answer: dp배열의 최대값

기본 개념

• dp[0]에 sequence[0]에 넣는다.
  
  
• dp[i-1]+sequence[i]와 sequece[i] 크기를 비교한다.
  
  
• 더 큰값을 dp[i]에 저장한다.
  
  
• max값을 갱신한다.

dp[i-1]+sequence[i]와 sequece[i] 크기를 비교하는 이유는 i-1번째 까지 최선의 연속 펄스 부분 수열의 합이 현재 sequence배열보다 작으면 앞은 무시하기 때문이다. 굳이 sequence[i]를 더하는 이유는 연속성을 유지하기 위해서다. (sequence[i]를 건너뛰는 최대 합을 구하는 것을 방지하기 위함)

코드

#define ll long long
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

long long solution(vector<int> sequence) {
    long long answer = 0;
    int sequence_len = sequence.size();
    vector<ll> p_s;
    p_s.push_back(0);
    for (int i = 1; i <= sequence_len; i++) {
        p_s.push_back(p_s[i - 1] + sequence[i - 1] * pow(-1, i));
    }
    sort(p_s.begin(), p_s.end());

    answer = p_s[sequence_len] - p_s[0];
    return answer;
}

정답~.~