[백준 1912] 연속합
February 17, 2023
문제
https://www.acmicpc.net/problem/1912
아이디어
- 합을 기록하는 변수를 0으로, 최대합을 기록하는 변수를 존재할 수 있는 최소값 으로 설정한다.
- 수열의 모든 값을 순회하면서 연속합을 계산한다.
- 만약 연속합이 음수라면, 이후의 값과 더했을 때 값을 감소시키는 효과만 있으므로 연속합을 버리고 다시 0으로 설정한다.
- 만약 연속합이 양수라면, 연속합을 기억한다.
소스코드
// 입력 처리
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const n = Number(input[0]);
const arr = input[1].split(" ").map(item => Number(item));
// 문제
function solution() {
let sum = 0;
let max = Number.MIN_SAFE_INTEGER;
arr.forEach(value => {
let temp = sum + value;
max = Math.max(max, temp); // 최대 합을 기억한다.
// 만약 현재까지의 합이 음수이면 버린다.
if (temp < 0) sum = 0;
// 반대로 양수이면, 현재까지의 합을 기억한다.
else sum = temp;
});
console.log(max);
}
// 실행
solution();