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

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

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

틀린 풀이

• 부분합을 저장하는 수열을 사용하는 접근은 좋았으나 2중 for문에서 시간 초과

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

using namespace std;

long long solution(vector<int> sequence) {
    int n = sequence.size();
    
    vector<long long> seqSum1(n, 0); //펄스 1, -1, 1, -1
    vector<long long> seqSum2(n, 0); //펄스 -1, 1, -1, 1
    seqSum1[0] = (long long)sequence[0];
    seqSum2[0] = -(long long)sequence[0];
    for(int i = 1; i<n; ++i){
        if(i%2 == 0){
            seqSum1[i] = seqSum1[i-1] + (long long)sequence[i];
            seqSum2[i] = seqSum2[i-1] - (long long)sequence[i];
        }
        else{
            seqSum1[i] = seqSum1[i-1] - (long long)sequence[i];
            seqSum2[i] = seqSum2[i-1] + (long long)sequence[i];
        }
    }
    
    long long answer = -50000000000;
    for(int i = 0; i<n; ++i){
        for(int j = i; j<n; ++j){
            //i에서 j까지 연속 펄스 부분 수열의 합
            if(i==0){
                answer = max(answer, seqSum1[j]);
                answer = max(answer, seqSum2[j]);   
            }
            else{
                answer = max(answer, seqSum1[j] - seqSum1[i-1]);
                answer = max(answer, seqSum2[j] - seqSum2[i-1]);
            }
        }
    }
    
    return answer;
}

테스트 1 〉	통과 (0.01ms, 4.2MB)
테스트 2 〉	통과 (0.01ms, 4.19MB)
테스트 3 〉	통과 (0.01ms, 4.14MB)
테스트 4 〉	통과 (0.01ms, 4.16MB)
테스트 5 〉	통과 (0.01ms, 4.21MB)
테스트 6 〉	통과 (0.01ms, 4.17MB)
테스트 7 〉	통과 (0.01ms, 4.02MB)
테스트 8 〉	통과 (0.16ms, 4.21MB)
테스트 9 〉	통과 (0.58ms, 4.14MB)
테스트 10 〉	통과 (14.02ms, 4.21MB)
테스트 11 〉	통과 (56.09ms, 4.14MB)
테스트 12 〉	통과 (5861.07ms, 8.12MB)
테스트 13 〉	통과 (5725.18ms, 8.09MB)
테스트 14 〉	통과 (5704.21ms, 8.16MB)
테스트 15 〉	통과 (6119.73ms, 8.13MB)
테스트 16 〉	통과 (5746.24ms, 8.41MB)
테스트 17 〉	실패 (시간 초과)
테스트 18 〉	실패 (시간 초과)
테스트 19 〉	실패 (시간 초과)
테스트 20 〉	실패 (시간 초과)

풀이

• 동적 계획법 사용 풀이

• ⭐dp[i]: 인덱스 i를 오른쪽 끝으로 갖는 구간의 최대 합
  -> i == 0인 경우 dp[i] = arr[i]
  -> i > 0인 경우 dp[i] = max(0, dp[i-1]) + arr[i]

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

using namespace std;

typedef long long ll;

const ll MINSUM = -50000000000;

ll solution(vector<int> sequence) {
    int n = sequence.size();
    
    vector<ll> seq1; //펄스 1, -1, 1, -1
    vector<ll> seq2; //펄스 -1, 1, -1, 1
    for(int i = 0; i<n; ++i){
        if(i%2 == 0){
            seq1.push_back(sequence[i]);
            seq2.push_back(-sequence[i]);
        }
        else{
            seq1.push_back(-sequence[i]);
            seq2.push_back(sequence[i]);
        }
    }
    
    ll answer = MINSUM;
    vector<ll> dp1(n, MINSUM);
    vector<ll> dp2(n, MINSUM);
    for(int i = 0; i<n; ++i){
        if(i==0){
            dp1[i] = seq1[i];
            dp2[i] = seq2[i];
        }
        else{
            dp1[i] = max(0LL, dp1[i-1]) + seq1[i];
            dp2[i] = max(0LL, dp2[i-1]) + seq2[i];
        }
        answer = max(answer, max(dp1[i], dp2[i]));    
    }
    return answer;
}

📌참고자료

• 최대 연속 부분수열 합을 구하는 4가지 알고리즘