[Algorithm] Programmers :: 연속 펄스 부분 수열의 합

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

프로그래머스

long long solution(vector<int> sequence)
{
    long long answer = 0;
 
    long long sum1 = 0;
    long long sum2 = 0;
    bool isCheck = true;
 
    for (int i = 0; i < sequence.size(); ++i)
    {
        sum1 += (long long)sequence[i] * (isCheck ? 1 : -1);
        sum2 += (long long)sequence[i] * (isCheck ? -1 : 1);
 
        sum1 = max(sum1, (long long)0);
        sum2 = max(sum2, (long long)0);
 
        answer = max(answer, max(sum1, sum2));
        isCheck = !isCheck;
    }
 
    return answer;
}

 

투포인터 기본문제들 중 하나인 최대 부분수열의 합을 구하는 문제처럼 풀이해도 되는데, 결과값의 시작인덱스와 끝인덱스를 알필요까진 없으니 위와같은 풀이가 가능하다.

 

정말 간단하게, 그냥 인덱스가 늘어나다가 음수값이 되면 다시 0으로 초기화시켜버리면 된다. 이런게 가능한 이유는 이 문제에서 최솟값은 0이기 때문이다. 음수가 절대 될 수 없다.

수열이 음수만 주어진다 하더라도 그냥 아무 음수하나 고른다음에 -1을 곱해버리면 그만이기 때문이다.

그렇기 때문에 max의 비교값에 0을 넣을 수 있는 것이다.