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

---

📌 문제 설명

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

 

📌 제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000
  • sequence의 원소는 정수입니다.

📌 입출력 예

sequence	result
[2, 3, -6, 1, 3, -1, 2, 4]	10

 

🔗 문제 링크

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

프로그래머스

---

반응형

💡 풀이 아이디어

• 카데인 알고리즘

📝 최종 풀이

• 1부터 시작하는 펄스 수열과 -1부터 시작하는 펄스 수열을 초기화합니다.
• 각각의 펄스 수열과 곱한 결과의 최대 부분합을 계산합니다.
  • 이전까지의 최대 합에 현재 원소를 더한 값과 현재 원소 값을 비교합니다.
• 두 가지 경우의 최대 부분 합 중 더 큰 값을 return 합니다.

---

728x90

👩‍💻 코드

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

using namespace std;

long long solution(vector<int> sequence) {
    int n = sequence.size();
    
    vector<int> pulse1(n), pulse2(n);
    
    for (int i = 0; i < n; i++) {
        pulse1[i] = (i % 2 == 0) ? 1 : -1;
        pulse2[i] = (i % 2 == 0) ? -1 : 1;
    }

    long long maxSum1 = 0;
    long long maxSum2 = 0;
    long long currentSum1 = 0;
    long long currentSum2 = 0;

    for (int i = 0; i < n; i++) {
        currentSum1 = max((long long)sequence[i] * pulse1[i], currentSum1 + (long long)sequence[i] * pulse1[i]);
        maxSum1 = max(maxSum1, currentSum1);

        currentSum2 = max((long long)sequence[i] * pulse2[i], currentSum2 + (long long)sequence[i] * pulse2[i]);
        maxSum2 = max(maxSum2, currentSum2);
    }

    return max(maxSum1, maxSum2);
}