[백준1912_자바스크립트(javascript)] - 연속합

🔴 문제

연속합

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const [n, inputs] = fs.readFileSync(path).toString().trim().split('\n');
const numbers = inputs.split(' ').map(Number);
const dp = new Array(Number(n)).fill(0);

dp[0] = numbers[0];

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

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

🟢 풀이

⏰ 소요한 시간 : 30분
처음에 투포인터로 접근을 했었는데 구현방법이 잘 떠오르지 않아서 지피티의 도움을 받았다. 지피티의 말을 듣고 보니 dp 유형이더라!
dp 배열을 만들고 dp[i]를 i번째 수를 마지막으로 하는 연속된 부분 수열의 최대 합으로 정의한다.
즉 dp[0]는 numbers[0]가 되고 dp[1]는 dp[0] + dp[1]이거나 dp[1]이다.
점화식을 세우면 다음과 같다.

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

정말 재미있고 흥미로운 dp~

🔵 Ref