[C#] 연속 펄스 부분 수열의 합

프로그래머스 문제

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

풀이 후기

1. 분석

수열의 어느 위치에서 [ +1 => -1 ] or [ -1 => +1 ] 하면서 최댓값을 찾는 문제. 뭔가 백준의 체스판 다시 칠하기(https://www.acmicpc.net/problem/1018) 문제가 생각이 났다. 이걸 뭐라고 하지.. A가 좋을까 B가 좋을까 2가지 패턴이 있는 문제?는 2가지 경우를 둘 다 계산하는 게 편함?? 뭔가 느낌이 있는데 설명을 못 하겠다.

[2, 3, -6, 1, 3, -1, 2, 4]

 +  -   +  -  +   -  +  -

2 -3 -6 -1 +3 +1 +2 -4


[2, 3, -6, 1, 3, -1, 2, 4]

 -  +   -  +  -   +  -  +

-2 +3 +6 +1 -3 -1 -2 +4

이런 식으로 +- 경우를 다 계산하고 저장하면 써먹기 편하다. 근데 이번 문제는 딱히 저장할 필요도 없긴 함.

암튼 0번부터 시작하면서 패턴1[+ -> -]와 패턴2[- -> +]의 합을 따로 계산하면서 최대 값을 갱신하는 게 핵심이다.

여기에 추가적인 조건인 [해당 인덱스 숫자를 더했는데 합이 음수로 나와서 망함]의 경우 합을 0으로 갱신하면 된다. 음수로 나오면 장사 때려치우고 다음 숫자부터 계산하는 게 당연히 합리적이다.

그리고 당연히 합은 Math.Max로 갱신시키면서 가장 큰 값만 살아남게 하면 코딩 끝.

2. 실행 결과

3. 코드

using System;

public class Solution {
    public long solution(int[] sequence) {
        var len = sequence.Length;
        long plusMinusSum = 0;
        long minusPlusSum = 0;
        long max = -1;
        
        for(var i = 0; i < len; i++){
            var pm = 0;
            var mp = 0;
            
            if(i % 2 == 1){
                pm = sequence[i] * 1;
                mp = sequence[i] * -1;
            }
            else{
                pm = sequence[i] * -1;
                mp = sequence[i] * 1;
            }
            
            if(plusMinusSum + pm < 0){
                plusMinusSum = 0;
            }
            else{
                plusMinusSum += pm;
                max = Math.Max(plusMinusSum, max);
            }
            
            if(minusPlusSum + mp < 0){
                minusPlusSum = 0;
            }
            else{
                minusPlusSum += mp;
                max = Math.Max(minusPlusSum, max);
            }
        }
        
        return max;
    }
}