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

Moky·2023년 3월 15일
0

Programmers

목록 보기
2/7

문제

어떤 수열의 연속 부분 수열에 같은 길이의 펄스 수열을 각 원소끼리 곱하여 연속 펄스 부분 수열을 만들려 합니다. 펄스 수열이란 [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 ≤ sequence의 길이 ≤ 500,000
  • -100,000 ≤ sequence의 원소 ≤ 100,000
    - sequence의 원소는 정수입니다.

입출력

sequence result
[2, 3, -6, 1, 3, -1, 2, 4] 10

풀이

Bottom up 방식을 사용하여 부분합의 최대값을 구한다.

  • 점화식
    sum_max[i] = max(a[i]+...+a[0], a[i]+...+a[1], ..., a[i]+a[i-1], a[i])
    sum_max[i] = max(a[i] + max(a[i-1]+...+a[0],...,a[0]), a[i])
    sum_max[i] = max(sum_max[i-1]+a[i], a[i])

직전값만 있으면 값을 구할 수 있기 때문에 sum_max에 해당하는 변수를 배열로 저장하지 않아도 된다.
펄스 수열은 1 혹은 -1로 시작하는 경우 두가지가 있다.

코드

function solution(sequence) {
  let top = 0;
  let sum1 = 0;
  let sum2 = 0;
  const nomal = sequence.map((v, i) => (!(i % 2) ? v : -v));
  const rev = sequence.map((v, i) => (i % 2 ? v : -v));
  for (const i in sequence) {
    sum1 = Math.max(sum1 + nomal[i], nomal[i]);
    sum2 = Math.max(sum2 + rev[i], rev[i]);
    top = Math.max(sum1, sum2, top);
  }
  return top;
}

문제링크

연속 펄스 부분 수열의 합

0개의 댓글