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

😀문제 설명

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

---

🤣입출력 예 설명

주어진 수열의 연속 부분 수열 [3, -6, 1]에 펄스 수열 [1, -1, 1]을 곱하여 연속 펄스 부분 수열 [3, 6, 1]을 얻을 수 있고 그 합은 10으로서 가장 큽니다.

---

😄나의 풀이

첫 번째 풀이는 이러하였다.. 난 나름 완벽한 풀이라고 생각했는데 이중 반복을 진행하며 시간초과가 떴음..

function solution(sequence) {
  let maxSum = Number.MIN_SAFE_INTEGER; // 가장 큰 연속 펄스 부분 수열의 합을 초기화합니다. 최소값으로 설정합니다.
  
  // 연속 부분 수열의 시작 인덱스를 순회합니다.
  for (let start = 0; start < sequence.length; start++) {
    let partialSum = 0; // 연속 부분 수열의 합을 초기화합니다.
    
    // 연속 부분 수열의 길이를 순회합니다.
    for (let length = 1; start + length <= sequence.length; length++) {
      // 각각의 연속 부분 수열의 원소에 대해 펄스 부분 수열을 적용합니다.
      // (1 -1 1 -1 ...) OR (-1 1 -1 1 ...)
      const pulseFactor = length % 2 === 0 ? -1 : 1;
      const currentElement = sequence[start + length - 1];
      const product = currentElement * pulseFactor;

      // 부분 합에 현재 팩터를 곱한 값을 더합니다.
      partialSum += product;

      // 부분 합이 최대 합보다 크면 최대 합을 갱신합니다.
      maxSum = Math.max(maxSum, partialSum);
    }
  }

  // 가장 큰 연속 펄스 부분 수열의 합을 반환합니다.
  return maxSum;
}

질문하기를 보다보니 굉장히 가독성 좋고 효율 좋은 풀이를 발견하였다

function solution(sequence) {
    let answer = 0;
    const dpPos = []; // 1 -1 1 ...
    const dpNeg = []; // -1 1 -1

    for(let i = 0 ; i < sequence.length ; i ++) {
        const s = sequence[i]
        // 연속되는 부분 수열을 사용할지, 현재 인덱스에서 끊을지
        if(i === 0) {
            dpPos.push(s)
            dpNeg.push(-s)
        } else if (i % 2 === 0) {
          dpPos.push(Math.max(dpPos[i - 1] + s, s));
          dpNeg.push(Math.max(dpNeg[i - 1] - s, -s));
        } else {
          dpPos.push(Math.max(dpPos[i - 1] - s, -s));
          dpNeg.push(Math.max(dpNeg[i - 1] + s, s));
        }
        answer = Math.max(answer, dpPos[i], dpNeg[i]);    
    }
  return answer;
}

1회 반복으로 DP 풀이를 하신 JinUk Kim님 리스펙