(C#) 연속 펄스 부분 수열의 합

코딩테스트 연습 - 연속 펄스 부분 수열의 합 | 프로그래머스 스쿨

프로그래머스

 

쉬운 문제인데 함정이 있었다.

 

연속 펄스 함수는 크게 의미 없다. 결국 sequence에 연속펄스 함수를 적용한 다음, 0번부터 n번까지의 부분수열의 합을 dp로 처리해 계산하면 되는 문제였다.

 

1. sequence에 연속펄스 함수를 적용한다.

2. dp에 부분 수열의 합을 기록한다.

예제로 있는 sequence 수열 [2, 3, -6, 1, 3, -1, 2, 4]로 살펴보자.

 

sequence에 연속펄스 함수를 적용한다. 1로 시작하는 펄스인지, -1로 시적하는 펄스인지는 상관없다.

그럼 sequence를 변형한 pulse 수열은 아래와 같다.

• pulse = [2, -3, -6, -1, 3, 1, 2, -4]

이제 pulse의 부분수열의 합을 dp에 기록한다.

dp[0] = a0

dp[1] = a0 + a1

dp[2] = a0 + a1 + a2

...

dp[n] = a0 + a1 + a2 + ... + an = Sn

 

ap ~ aq의 부분수열의 합은 Sp - Sq이다.

이 값이 최대가 되게 하려면 dp에서 최대값과 최소값을 찾아야한다.

dp의 최대값과 최소값의 차이가 바로 부분수열의 합 중 최대값이 된다.

 

그러나 문제가 하나 발생했다.

2, 3을 비롯한 몇개의 테스트에 실패했다.

 

문제는 부분 수열이 a0을 포함하는 경우를 처리하지 못하는 것이었다.

 

dp가 S1부터 시작하기 때문에 어떤 부분수열을 선택하더라도 a0의 값은 포함되지 않는다.

 

따라서 이 문제를 해결하기 위해 dp[0] = 0으로 고정하고, dp[1]부터 S1을 기록하도록 했다.

 

코드

using System;

public class Solution {
    public long solution(int[] sequence)
    {
        long[] pulse  = new long[sequence.Length + 1];
        long[] dp = new long[sequence.Length + 1];
        plus[0] = 0;

        bool flag = false;
        long max = pulse [0], min = pulse [0];
        for (var i = 0; i < sequence.Length; i++)
        {
            plus[i + 1] = pulse [i] + (flag ? sequence[i] : -sequence[i]);
            if (max < pulse [i + 1]) max = pulse [i + 1];
            if (min > pulse [i + 1]) min = pulse [i + 1];
            flag = !flag;
        }

        return Math.Abs(max - min);
    }
}