백준 1912번: 연속합 - javascript

백준 1912번: 연속합

문제 설명

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

접근

연속 된 수의 합의 경우 중 제일 큰 수를 구하는 문제이다. 연속 된 수라는것은 i번째값이 i-1, i-2, i-3… 에 영향을 받는다는 뜻이다.

그러면 어떻게 하면 연속된 최대 합을 구할 수 있을까?

10
10 -4 3 1 5 6 -35 12 21 -1

예제를 통해 보자. 우리는 10-4+3+1+5+6-35 까지의 합을 사용하느니 그냥 12+21이 크다는것을 눈으로 그냥 비교해 볼 수 있다. 하지만 이를 컴퓨터 입장에서 풀려면 (10-4+3+1+5+6-35)+12의 합이 클지 그냥 12가 클지 비교해 봐야한다. 위의 상태에서 12가 들어있는 인덱스를 i라고 하자. 그러면 10-4+3+1+5+6-35 의 합은 0부터 i-1까지의 합이다. 이를 식으로 나타내면

array[i] = Math.max( sum(0 ~ i-1)+array[i], array[i])

와 같은 식으로 나타낼 수 있다. 그러면 0에서 i-1번째 까지의 합은 어떻게 나왔을까.

array[i-1] = Math.max( sum(0 ~ i-2)+array[i-1], array[i-1])

이런식으로 0부터 i-2까지의 합과 i-1을 더한 값과 i-1번째 값을 비교해보고 0부터 i-1까지의 합이 더 크기 때문에 온 것이다. 이렇게 역으로 0까지 타고 내려가보면 결국

array[1] = Math.max( array[0]+array[1], array[1])

로 나타낼 수 있음을 알 수 있다. 약간 DFS처럼 끝까지 파고 내려갔는데, 각 행위마다 array[i]에 해당 값을 저장하므로써 값을 계속 유지해서 메모제이션을 사용하게 된다.

결국 i는 1부터 마지막까지 위의 dp식을 반복해가며 도출해낸 array의 값 중 max값을 도출하면 된다.

이번 문제에서 주의 할 점
위처럼 풀었었는데 한 번 틀렸었다. 그 이유는 위의 dp식을 사용하게되면 우리는 array의 0번째 자체가 나머지 합들보다 더 큰지 비교를 하고 지나가지 않게된다.

5
-1 -2 -3 -4 -5

위처럼 계속 음수만 나올경우 기존의 식대로 진행하면 -2가 제일 크다고 나오게 된다. 따라서 우리는 array의 max를 비교하기보다는 별도의 max값을 비교하는 변수 result를 선언하고 거기에 초기값으로 array의 0번째 배열값을 넣어 줄 필요가 있다.

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  let arr = input[1].split(' ');
  let answer = max_sum_dp(arr);
  console.log(answer);
  process.exit();
});

function max_sum_dp(arr){
  let result = arr[0];
  for(let i = 1; i < arr.length; i++){
    arr[i] = Math.max(arr[i]*1, arr[i]*1+arr[i-1]*1);
    result = Math.max(arr[i],result);
  }
  return result;
}