[JAVA/DP] 연속 펄스 부분 수열의 합

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

프로그래머스

 

class Solution {
    public long solution(int[] sequence) {
        
        // 16, 19, 20이 계속 에러가 나서 왜그런가 하고 봤더니 자료형을 int가 아니라 long으로 하면 해결됨
        // https://school.programmers.co.kr/questions/45489
        
        // +1을 먼저 곱할때와, -1을 먼저 곱할때의 경우의 수
        // 사실 굳이 이렇게할 건 없이 abs로 덮는 방법으로 해결 가능할듯 하지만 일단 진행.
        long[] seqPlus = new long[sequence.length];
        long[] seqMinus = new long[sequence.length];
        
        long tmp = 1;
        long max = Long.MIN_VALUE;

        // 0번째는 먼저 입력하고 시작 
        seqPlus[0] = sequence[0] * tmp;
        seqMinus[0] = seqPlus[0] * -1;
        max = Math.max(Math.abs(seqPlus[0]), max);
        max = Math.max(seqMinus[0], max);
        
        for(int i=1; i<sequence.length; i++) {
            
            tmp *= -1;
            
            // 각각 +1과 -1 곱하고 각 배열의 현 위치의 최대값 저장
            long tmpPlus = sequence[i] * tmp;
            long tmpMinus = tmpPlus * -1;
            
            seqPlus[i] = Math.max(seqPlus[i-1]+tmpPlus, tmpPlus);
            seqMinus[i] = Math.max(seqMinus[i-1]+tmpMinus, tmpMinus);
            
            // 중간에 나온 최대값 저장
            max = Math.max(Math.abs(seqPlus[i]), max);
            max = Math.max(seqMinus[i], max);
            
        }
        
        
        return max;
    }
}