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

Lv3, 그리디, Prefix sum

문제

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [1, -1, 1, -1 …] 또는 [-1, 1, -1, 1 …] 과 같이 1 또는 -1로 시작하면서 1과 -1이 번갈아 나오는 수열입니다.
예를 들어 수열 [2, 3, -6, 1, 3, -1, 2, 4]의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하면 연속 펄스 부분수열은 [3, 6, 1]이 됩니다. 또 다른 예시로 연속 부분 수열 [3, -1, 2, 4]에 펄스 수열 [-1, 1, -1, 1]을 곱하면 연속 펄스 부분수열은 [-3, -1, -2, 4]이 됩니다.
정수 수열 sequence가 매개변수로 주어질 때, 연속 펄스 부분 수열의 합 중 가장 큰 것을 return 하도록 solution 함수를 완성해주세요.

풀이

• 두 부분합 배열을 통해 [1, -1, 1 ...], [-1, 1, -1 ...]의 펄스 형태를 갖는 배열 만든다.
• 각 부분합의 최대 지점과 최소 지점을 찾는다.
• 해당 위치 값들의 차이가 부분 배열의 최대 값이 된다.

function solution(sequence) {
    const n = sequence.length;
    
    var psum1 = Array(n + 1).fill(0);
    var psum2 = Array(n + 1).fill(0);
    
    var max1 = -Infinity;
    var min1 = Infinity;
    var max2 = -Infinity;
    var min2 = Infinity;
    
    let pulse = 1;
    for(let i = 0; i < n; i++){
        psum1[i + 1] = psum1[i] + sequence[i] * pulse;
        psum2[i + 1] = psum2[i] + sequence[i] * pulse * -1;
        pulse *= -1;
    }
    
    for(let i = 0; i < n + 1; i++){
        max1 = Math.max(psum1[i], max1);
        max2 = Math.max(psum2[i], max2);
        
        min1 = Math.min(psum1[i], min1);
        min2 = Math.min(psum2[i], min2);
    }
    
    return Math.max((max1 - min1), (max2 - min2));
}