[백준] 1912 연속합 (Javascript)

문제

BOJ1912_연속합

풀이

요구사항

길이 n의 수열이 있을 때, 연속된 부분수열의 합 중 가장 큰 합을 출력하라.

해결방안

투 포인터

DP로 분류된 문제지만 투 포인터로도 풀 수 있다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const n = +input[0];
const arr = input[1].split(' ').map(Number);
let max = 0;
let acc = 0;

let left = (right = 0);
while (right < arr.length) {
    if (left === right) acc += arr[left];
    else acc += arr[right];
    if (acc < 0) {
        left = right + 1;
        acc = 0;
    }
    max = Math.max(acc, max);
    right++;
}
console.log(max === 0 ? Math.max(...arr) : max);

left와 right는 0번 인덱스부터 시작하고 left와 right가 같은 인덱스에 있을 경우에는 arr[left]를 누적해주고, 다른 인덱스에 있을 때는 arr[right]를 누적해준다.

만약 누적합이 음수가 된다면 현재까지 누적에 사용한 값들은 필요 없으므로 누적합을 0으로 만들어준 뒤 left를 right+1로 이동시킨다.

그리고 누적합과 최댓값을 비교하여 최댓값을 갱신시켜준다.

그리고 right를 1증가시킨다.

반복이 종료되었을 때 그냥 max를 출력해주도록 한다면 입력값이 음수밖에 없을 때 0으로 초기화된 max보다 큰 값이 없기 때문에 0이 출력되어 오답이 나온다.

따라서 max가 0일 경우에는 입력값 중 가장 큰 값을 출력하고, 아닐 경우에는 그냥 max를 출력해주면 된다.

DP

DP로 풀면 코드가 더 깔끔해진다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const n = +input[0];
const arr = input[1].split(' ').map(Number);

let dp = arr.map((e) => e);
for (let i = 1; i < n; i++) {
    dp[i] = Math.max(dp[i], dp[i] + dp[i - 1]);
}
console.log(Math.max(...dp));

dp를 이용해서 이전까지의 누적합에 현재 값을 더해주는 게 더 큰지, 아니면 현재 값만 있는 게 더 큰지 비교해서 dp에 저장하고, 이 중 최댓값을 출력해주면 답이 된다.