📍문제 링크
https://www.acmicpc.net/problem/1912
1912번: 연속합
첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.
www.acmicpc.net
📍알고리즘 분류
- DP
📍문제 풀이
정수가 N개 주어질 때, 연속하는 정수들로 구성된 최댓값을 구하라
DP를 써서 O(N)에 해결할 수 있다
📍의사 코드
주어진 배열을 순회하며, memo 배열에는 arr[i] 까지의 연속합을 저장한다
(단, 더했을때 오히려 마이너스가 되면, 다음에 나오는 수로 업데이트)
예를 들면, 10 -4 3 1 5 6 -35 12 21 -1 배열에서
10
10 -4
10 -4 3
10 -4 3 1
10 -4 3 1 5
10 -4 3 1 5 6
10 -4 3 1 5 6 -35 <- 더하지 않는게 나은 수 등장
10 -4 3 1 5 6 -35 12
10 -4 3 1 5 6 -35 12 21
10 -4 3 1 5 6 -35 12 21 -1
memo [ 10, 6 ]
max 10
memo [ 10, 6, 9 ]
max 10
memo [ 10, 6, 9, 10 ]
max 10
memo [ 10, 6, 9, 10, 15 ]
max 15
memo [ 10, 6, 9, 10, 15, 21 ]
max 21
memo [ 10, 6, 9, 10, 15, 21, -14 ]
max 21
memo [ 10, 6, 9, 10, 15, 21, -14, 12 ] <- -35를 더한 수 대신 다음 수인 12를 저장
max 21 <- 최댓값은 유지됨
memo [ 10, 6, 9, 10, 15, 21, -14, 12, 33 ]
max 33
memo [ 10, 6, 9, 10, 15, 21, -14, 12, 33, 32 ]
max 33
answer : 33
📍코드 (JavaScript)
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
const input = [];
rl.on("line", (line) => {
input.push(line);
}).on("close", () => {
const N = +input[0];
const nums = input[1].split(" ").map(Number);
/**
* 배열에서 연속하는 최대합 출력
* @param len - 배열의 길이
* @param arr - 배열
*/
const dp = (len, arr) => {
const memo = [arr[0]];
// 배열 전체에서의 최댓값
let max = arr[0];
for (let i = 1; i < len; i++) {
memo[i] = Math.max(memo[i - 1] + arr[i], arr[i]);
max = Math.max(memo[i], max);
}
return max;
};
console.log(dp(N, nums));
});