[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()
})
Author And Source
이 문제에 관하여([boj] 1912. 연속합 (node.js)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@greenish0902/boj-1912.-연속합-node.js저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)