[프로그래머스] Lv3. 연속된 펄스 부분 수열의 합- JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 3

출처 : 프로그래머스 - 연속된 펄스 부분 수열의 합

문제

제한사항

📌 내가 생각한 풀이

양의 펄스와 음의 펄스를 담을 수 있는 배열 두개를 만들고, Dp를 사용하여 최대값을 구하자

// Dp로 문제를 풀자
// arr1, arr2를 나누고
// 최대값을 선택하는 점화식을 세우자

function solution(sequence) {
  var answer = 0;
  //[1, -1, 1, -1, ...]을 곱한 값중 최대값을 담을 배열
  let arr1 = [];
  let arr2 = [];
  sequence.forEach((data, idx) => {
    if (idx === 0) {
      arr1 = [data];
      arr2 = [-data];
    } else if (idx % 2 === 0) {
      //점화식 =>  그전까지의 합에다 data를 계산한것과, 그냥 data값중에 큰 것 선택
      arr1.push(Math.max(arr1[idx - 1] + data, data));
      arr2.push(Math.max(arr2[idx - 1] - data, -data));
    } else {
      arr1.push(Math.max(arr1[idx - 1] - data, -data));
      arr2.push(Math.max(arr2[idx - 1] + data, data));
    }
    answer = Math.max(answer, arr1[idx], arr2[idx]);
  });
  return answer;
}

📌 느낀점

DP문제중에서 경우의 수를 두 가지로 나누어야 하는 문제이다. 이번 문제는 점화식을 생각하기가 조금 어려웠다. 스티커 모으기[2]와 비슷한 유형의 문제이므로 다시 한번 풀어보자!