Baekjoon 1912번 연속합

문제

https://www.acmicpc.net/problem/1912

걸린 시간

-

풀이

JavaScript

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input';
const stdin = fs.readFileSync(filePath).toString().trim().split('\n').map(s => s.trim());
const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

let n = parseInt(input());
const a = input().split(' ').map(Number);
const dp = Array(n);
dp[0] = a[0];
for(let i = 1; i < n; i++){
  dp[i] = Math.max(dp[i-1]+a[i], a[i]);
}
let ans = Number.NEGATIVE_INFINITY;
for(let i = 0; i < n; i++) ans = Math.max(ans, dp[i]);
console.log(ans);

연속된 몇개의 값을 골랐을 때 합이 최대가 되도록 해야한다.

가능한 모든 경우를 구하게 되면 1e10 으로 시간초과가 난다. O(n) 으로 통과하기 위한 아이디어를 떠올려야 했다.

연속된 값을 골라야 하므로 배열의 값을 처음부터 차례로 확인한다. 각 단계마다 두 가지 선택지가 존재하는데,

1. 연속적으로 선택된 값에 현재 값을 추가한다.
2. 현재 값부터 새롭게 선택을 시작한다.

1. 2. 의 값을 비교해서 더 큰 경우를 선택하면 최대값을 구할 수 있다.

점화식 : dp[i] = Math.max(dp[i-1]+a[i], a[i])