[1일 1알고] 연속 펄스 부분 수열의 합

 

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

프로그래머스

문제가 Lv3이지만 실제적으로 어려운 문제는 아닙니다.

 

펄스 수열은 [1, -1, 1... 꼴과 [-1, 1, -1... 꼴로 나누어지는데, 그렇다면 그냥 이 두가지 경우에 대해 계산한 후 최종결과를 내면 됩니다.

 

기본적으로 넘어오는 sequence에 펄스수열을 미리 계산한 뒤  (미리 계산하지 않아도 되겠네요)

이에 대해 가질 수 있는 부분 수열의 최댓값을 구하는 것이 답입니다.

---

using namespace std;

long long solution(vector<int> sequence) {
    long long answer = 0;
    int N = sequence.size();
    vector<int> case1(N, 0);
    vector<int> case2(N, 0);

    int pulse = 1;
    for (int i = 0; i < N; ++i)
    {
        case1[i] = sequence[i] * pulse;
        case2[i] = sequence[i] * pulse * -1;

        pulse *= -1;
    }

    int result1 = case1[0];
    int result2 = case2[0];
    int cur1 = case1[0];
    int cur2 = case2[0];

    for (int i = 1; i < N; ++i)
    {
        if (cur1 < 0)
        {
            cur1 = case1[i];
        }
        else
        {
            cur1 += case1[i];
        }

        if (cur2 < 0)
        {
            cur2 = case2[i];
        }
        else
        {
            cur2 += case2[i];
        }

        result1 = max(result1, cur1);
        result2 = max(result2, cur2);
    }

    answer = max(result1, result2);

    return answer;
}

보는 것처럼 현재까지의 합이 마이너스라면 새롭게 시작하고 아니라면 더하는 방식으로 계산한다면 간단하게 부분수열 합의 최댓값을 만들 수 있습니다.