프로그래머스 LEVEL 3(연속 펄스 부분 수열의 합)

사용 언어 : javascript
해결 날짜 : 2023-04-29
해결 방법 :
- dp를 활용하여 문제 해결
  - -1과 1로 시작하는 펄스 수열을 각각 생성
  - 각 펄스 수열에 대하여 dp(최대 부분합)을 업데이트 하되,
  - 각 반복마다 answer 최대값으로 업데이트
회고 :
- 처음에 펄스 수열이 -1과 1 중 어떤걸로 시작하든 절댓값의 최댓값을 구하면 되겠다고 생각하여 펄스 수열을 각각 만들지 않고 해결하려 했다.
- 그러나 -1로 시작하는 펄스 수열과 1로 시작하는 펄스 수열은 완전히 다른 계산을 수행해 각각 따로 생성하여 문제를 해결했다.

코드

function solution(sequence) {
  let answer = 0;

  const pulse1 = Array.from({ length: sequence.length }, (_, i) => (i % 2 === 0 ? 1 : -1)),
    pulse2 = Array.from({ length: sequence.length }, (_, i) => (i % 2 === 0 ? -1 : 1));

  const dp1 = [],
    dp2 = [];

  sequence.forEach((v, i) => {
    const temp1 = v * pulse1[i],
      temp2 = v * pulse2[i];

    if (i === 0) {
      dp1.push(temp1);
      dp2.push(temp2);
    } else {
      dp1.push(Math.max(dp1[i - 1] + temp1, temp1));
      dp2.push(Math.max(dp2[i - 1] + temp2, temp2));
    }

    answer = Math.max(answer, dp1[i], dp2[i]);
  });

  return answer;
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges