연속 펄스 부분 수열의 합

링크

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

문제

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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 함수를 완성해주세요.

풀이

연속 부분 배열합을 구할 수 있으면 해당 알고리즘을 변형해서 문제를 풀면 된다.

const LSCS = (arr) => {
	let result = -Infinity;
    let max = 0;
    
    for(let i = 0; i < arr.length; i++){
    	max = Math.max(arr[i], max + arr[i]);
        result = Math.max(max, result);
    }
    
    return result;
};

위의 코드는 연속 부분 배열합의 최대를 구하는 알고리즘이다. 위의 알고리즘에 펄스 수열이 곱해지는 것을 고려하면서 코드를 작성한다.

코드

// 연속 부분 배열합을 구하는 문제의 변형.
// 기본적으로 연속부분배열합에서는 덧셈으로만 계산이되었다면 인덱스 번호에 따라서 중간에 -로 계산되는 부분을 추가한다
// arrP : [1, -1, 1, ...]으로 시작되는 펄스 수열로 계산
// arrM : [-1, 1, -1, ...] 으로 시작되는 펄스 수열로 계산
function solution(sequence) {
    let arrP = []
    let arrM = []
    let answer = 0
    
    // 연속 부분 배열합 계산
    sequence.forEach((el, i) => {
        if(i === 0) {
            arrP.push(el)
            arrM.push(-el)
        } else if(i % 2 === 0) {
            arrP.push(Math.max(el, arrP[i - 1] + el))
            arrM.push(Math.max(-el, arrM[i - 1] - el))
        } else {
            arrP.push(Math.max(-el, arrP[i - 1] - el))
            arrM.push(Math.max(el, arrM[i - 1] + el))
        }
        
        answer = Math.max(answer, arrP[i], arrM[i])
    })
    
    return answer
}