[프로그래머스][dp] 연속 펄스 부분 수열의 합

     

목차

 

문제

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

프로그래머스

 

 

문제 구현 방향

이중순회하면 시간 초과가 나기때문에 무조건 O(n)으로 해결해야 한다.

이때 누적합을 이용했다.

이때 -1 1 -1순일 때와 1 -1 1 순일때로 dp를 나누어서 생각하면 된다.

 

코드 구현

function solution(sequence) {
    var answer = -Infinity;
    
    const oddDp = [];
    const evenDp = [];
    oddDp.push(-sequence[0]);
    evenDp.push(sequence[0]);
    
    answer = Math.max(answer, evenDp[0], oddDp[0]);
    
    for (let i = 1; i < sequence.length; i++) {
        const s = sequence[i];
        if (i % 2 === 0) {
            oddDp.push(Math.max(oddDp[i-1] + -s, -s));
            evenDp.push(Math.max(evenDp[i-1] + s, s));
        } else {
            oddDp.push(Math.max(oddDp[i-1] + s, s));
            evenDp.push(Math.max(evenDp[i-1] + -s, -s));
        }
        answer = Math.max(answer, evenDp[i], oddDp[i]);
    }
    
    return answer;
}