[JS] 연속 펄스 부분 수열의 합

문제

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

프로그래머스

 

 

풀이

이 문제를 보고 펄스 수열이라는 말이 눈에 거슬렸다. -1과 1을 번갈아가며 곱셈되는 동작을....

 

펄스 동작이 1부터 곱해지냐 아니면 -1부터 곱해지냐는 정해져 있는 것이다.

 

첫번째 풀이는 전부 1 혹은 -1 씩 번갈아 가며 요소들에 곱해준 배열을 구한 뒤 누적합을 구했었지만, 이렇게 풀이한 경우 부분 수열의 합을 구할 수 없기에 통과하지 못했다.

function solution(sequence) {
  const arr1 = sequence.map((e, i) => {
    if (i % 2 === 0) return e;
    else return -e;
  });
  const arr2 = sequence.map((e, i) => {
    if (i % 2 === 1) return e;
    else return -e;
  });
    
  for (let i = 1; i < sequence.length; i++) {
    if (arr1[i - 1] + arr1[i] > arr1[i]) arr1[i] = arr1[i - 1] + arr1[i];
    if (arr2[i - 1] + arr2[i] > arr2[i]) arr2[i] = arr2[i - 1] + arr2[i];
  }
    
  return Math.max(Math.max(...arr1), Math.max(...arr2));
}

 

그래서 DP를 이용해 부분 수열의 합 중 최대합을 구할 수 있도록 코드를 수정해서 작성해 봤다.

코드

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