[Javascript/자바스크립트] (프로그래머스) 연속 펄스 부분 수열의 합

https://school.programmers.co.kr/learn/courses/30/lessons/161988?language=javascript

코드

function solution(sequence) {
  let answer = Number.NEGATIVE_INFINITY;

  let odd = 0;
  let even = 0;
  for (let i = 0; i < sequence.length; i++) {
    const odd_pulse = i % 2 === 1 ? 1 : -1;
    const even_pulse = i % 2 === 1 ? -1 : 1;
    odd = Math.max(odd_pulse * sequence[i], odd + odd_pulse * sequence[i]);
    even = Math.max(even_pulse * sequence[i], even + even_pulse * sequence[i]);
    answer = Math.max(answer, odd, even);
  }
  return answer;
}

 

처음에는 1로 시작하는 펄스 수열을 곱하는 경우와 -1로 시작하는 펄스 수열을 곱하는 경우 2가지로 나누어서 투포인터 알고리즘을 사용하려고 했는데, 20점만 맞고 틀렸다...다시 생각해보다가 모르겠어서 찾아보니 카데인 알고리즘을 사용하면 된다고 나왔다.

 

카데인 알고리즘에 대한 자세한 설명은 아래에 있다.

Kadane’s Algorithm (카데인 알고리즘)

또 새로운 알고리즘인가 싶지만, 자세히 살펴보면 그냥 DP의 서브셋 중 하나라고 보면 된다. 어떤 수열의 부분 수열의 최대합을 저장하는 dp라는 배열이 있다고 하면, dp[i]에는 i번째 인덱스를 포함하는 부분 수열 중 최대 합을 가지는 부분 수열의 합이 저장된다. 그렇기에 dp[i]값을 구할 때는 dp[i-1]의 값+현재 인덱스(i)의 값과 그냥 현재 인덱스(i)의 값 중 큰 값을 저장하게 된다. 예를 들어, [1, -3, 2]라는 배열이 있을 때, dp[1]은 -2가 있을 것이다. 여기서 dp[2]는 dp[1]+2와 그냥 2 중에 큰 값을 고르기 때문에 2가 저장된다.

 

이처럼 카데인 알고리즘은 이전 인덱스까지의 합이 현재 인덱스와 더했을 때 +가 된다면 취하고, 아니면 취하지 않는 알고리즘이라고 보면 된다.

 

이 문제에서도 카데인 알고리즘을 사용하여 쉽게 구할 수 있었다. 다만, 펄스 수열은 2가지이기 때문에 홀수번째 인덱스가 펄스 값이 1인 odd와 짝수번째 인덱스의 펄스 값이 1인 even으로 나누어서 구했다.