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

문제 설명

주어진 정수 수열에서 연속 부분 수열에 펄스 수열을 곱하여 얻은 합 중 최대 값을 구하세요.
펄스 수열은 [1, -1, 1, -1, ...] 또는 [-1, 1, -1, 1, ...] 형태입니다.

---

제한 사항

• 1 ≤ sequence의 길이 ≤ 500,000
• -100,000 ≤ sequence의 원소 ≤ 100,000

---

해결 방법

알고리즘: 동적 프로그래밍 (Dynamic Programming)

1. 두 종류의 펄스 수열에 대해 최대 합을 계산합니다.
2. 현재 값과 이전 최대 합을 비교하여 최댓값을 갱신합니다.
3. 모든 경우를 탐색하며 최대 값을 반환합니다.

---

시간 복잡도

• O(n): 수열을 한 번 순회하며 계산.
• 공간 복잡도: O(1): 상수 크기 변수 사용.

function solution(sequence) {
  let num1 = sequence[0];
  let num2 = -sequence[0];
  let answer = Math.max(num1, num2);

  for (let i = 1; i < sequence.length; ++i) {
    const curNum1 = i % 2 === 0 ? sequence[i] : -sequence[i];
    const curNum2 = i % 2 === 1 ? sequence[i] : -sequence[i];

    num1 = Math.max(curNum1, num1 + curNum1);
    num2 = Math.max(curNum2, num2 + curNum2);

    answer = Math.max(num1, num2, answer);
  }

  return answer;
}