연속 펄스 부분 수열의 합

문제 정보

• 프로그래머스 Lv.3
• DP
• 문제 링크

풀이

DP, 보다 정확하게는 DP를 활용한 카데인 알고리즘을 활용하는 문제다.

다만 펄스 수열이 -1로 시작하는 경우와 1로 시작하는 수열 두 경우가 있기 때문에 각각의 경우에 대해 카데인 알고리즘을 두 번 실행해야 한다.

코드

import java.util.*;
 
class Solution {
    public long solution(int[] sequence) {
        long pulse1 = kadane(sequence, true);
        long pulse2 = kadane(sequence, false);
        
        return Math.max(pulse1, pulse2);
    }
    
    private long kadane(int[] sequence, boolean startPlus) {
        long max = Long.MIN_VALUE;
        long cur = 0;
        
        for (int i = 0; i < sequence.length; i++) {
            long value;
            if (startPlus)
                value = sequence[i] * (i % 2 == 0 ? 1 : -1);
            else
                value = sequence[i] * (i % 2 == 0 ? -1 : 1);
            
            cur = Math.max(value, cur + value);
            
            max = Math.max(max,cur);
        }
        
        return max;
    }
}

관련 노트

• 카데인 알고리즘