[Javascript] 백준 1912번 연속합

문제 설명

n개의 정수로 이루어진 임의의 수열이 주어집니다. 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 합니다. 단, 수는 반드시 한 개 이상 선택해야 합니다.

---

제한 조건

• 정수의 개수 nnn: 1 ≤ n ≤ 100,000
• 각 정수 ai​: −1,000 ≤ ai ≤ 1,000

---

해결 방법

알고리즘 분류: 다이나믹 프로그래밍

핵심 아이디어

• 각 위치에서의 최대 연속합을 계산하기 위해 Kadane's Algorithm을 사용합니다.
• 현재까지의 최대 연속합과 비교하여 최댓값을 유지합니다.

알고리즘 단계

1. 현재까지의 최대 연속합 유지:
   • currentMax: 이전 위치까지의 최대 연속합에 현재 값을 더한 값과 현재 값 중 더 큰 값.
2. 전체 최대값 갱신:
   • maxSum: 각 단계의 currentMax와 기존 maxSum 중 더 큰 값으로 갱신.

---

시간 복잡도

• 시간 복잡도: O(n)
  • 수열의 모든 요소를 한 번만 순회.
• 공간 복잡도: O(1)
  • 추가 배열 없이 상수 공간만 사용.

---

구현 코드

const readline = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

readline
  .on("line", function (line) {
    input.push(line);
  })
  .on("close", function () {
    const numArr = input[1].split(" ").map(Number);

    let maxSum = numArr[0];
    let currentMax = numArr[0];

    for (let i = 1; i < numArr.length; ++i) {
      currentMax = Math.max(currentMax + numArr[i], numArr[i]);
      maxSum = Math.max(maxSum, currentMax);
    }

    console.log(maxSum);

    process.exit();
  });