[JS] 연속합 - 백준 1912

문제

시간복잡도

O(n)

해결 방법

 

 

dp[i]에는 지금까지의 최대의 연속합을 저장한다. dp[i-1]+input[i]보다 input[i]가 더 크다면 input[i]부터의 연속합이 더 클 것이니  input[i]를 저장한다.

dp[i]=Math.max(dp[i-1]+input[i-1],input[i-1])

(코드에서는 input이 input[1]에 저장되어있음)

 

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./example.txt";
let input = fs.readFileSync(filePath).toString().split("\n");
input[1] = input[1].split(" ");
for (let i = 0; i < input[1].length; i++) {
  input[1][i] = parseInt(input[1][i]);
}

let dp = [];
dp[0] = -Infinity;

for (let i = 1; i <= input[0]; i++) {
  dp[i] = Math.max(dp[i - 1] + input[1][i - 1], input[1][i - 1]);
}

console.log(Math.max(...dp));