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

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

주어진 수열과 펄스 수열을 각 항끼리 곱합니다. 그 결과를 연속 펄스 수열이라 하면, 연속 펼스 수열의 부분수열의 합의 최댓값을 구하는 문제입니다. dp를 이용하여 풀었습니다.

우선 펄스가 두 종류가 있다는 점은 maxSubseq method를 구현하여 negative parameter를 전달하는 방식으로 처리했습니다.

sequence를 읽어나가며 dp[i] 에 i+1 번째 항으로 끝나는 부분수열의 합의 최댓값을 저장할 것입니다.

dp[0]에 해당하는 1번째 항으로 끝나는 부분수열의 합의 최댓값은 부분수열이 {sequence[0]} 뿐이니 첫번째 항을 그대로 넣어줍니다.

최댓값을 구하고 있으므로, dp[i - 1]이 0보다 작다면 i항의 앞부분들은 버리고 새로 시작합니다. 이 방식으로 현재값인 sequnece[i]에 pulse를 곱해서 더합니다.

최종적으로 dp array의 각 항에는 1 ~ sequence.length 번째 항으로 끝나는 부분수열 합의 최댓값이 들어있으므로, 이들 중 최댓값을 구하면 됩니다.

class Solution {
    public long solution(int[] sequence) {
        long positive = maxSubseq(sequence, 1);
        long negative = maxSubseq(sequence, -1);
        
        return Math.max(positive, negative);
    }
    
    public long maxSubseq(int[] sequence, int startingSignal) {
        long[] dp = new long[sequence.length];
        long pulse = (long) startingSignal;
        
        dp[0] = sequence[0] * pulse;
        pulse *= -1;
        
        long maxi = dp[0];
        
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Math.max(dp[i - 1], 0) + sequence[i] * pulse;
            maxi = Math.max(dp[i], maxi);
            pulse *= -1;
        }
        
        return maxi;
    }
}