[boj] 1912. 연속합 (node.js)

문제 요약

[boj] 1912. 연속합 (node.js)

• 연속합의 최댓값을 구하라.

풀이

• n의 최댓값이 100,000 이므로 시간 제한 내에 풀이하기 위해서는 O(N)의 풀이가 필요하다.
• 일차원 배열 dp값을 채운 후 최댓값을 출력한다.
• 점화식
  • dp[i] = Math.max(dp[i-1]+arr[i], dp[i])
  • 일차원 배열을 돌며, Math.max로 기존 값 또는 누적 값과의 합 중 더 큰 값을 배열에 저장한다.
  • 연속합이 기존 값보다 클 경우에만 갱신되므로, 각 배열 인덱스마다 해당 위치까지의 최댓값이 저장되게 된다.

내 풀이

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

const solution = () => {
  const n = Number(input())
  const arr = input().split(" ").map(Number)
  let dp = [...arr]
  let max = dp[0]
  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(dp[i - 1] + arr[i], dp[i])
    max = Math.max(dp[i], max)
  }
  console.log(max)
}

let line = 0
const input = () => stdin[line++]

let stdin = []
rl.on("line", function (line) {
  stdin.push(line)
}).on("close", function () {
  solution()
  process.exit()
})