백준 13398번: 연속합2 - javascript

백준 13398번: 연속합2

문제 설명

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

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

만약, -35를 제거한다면, 수열은 10, -4, 3, 1, 5, 6, 12, 21, -1이 되고, 여기서 정답은 10-4+3+1+5+6+12+21인 54가 된다.

입력

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

출력

첫째 줄에 답을 출력한다.

접근

이 문제는 1912번 연속합의 응용 버전이다. 한 번 풀어봤던 문제가 베이스여서 금방 풀 줄 알았는데 시간을 꽤 많이 잡아먹었다…
문제에서 수열에서 수를 하나 제거할 수 있다.(제거하지 않아도 된다) 라는 조건이 붙었는데, 당연히 제거하고 싶은 수는 음수라고 생각해서 가볍게 주어진 배열에서 음수의 인덱스만 담은 배열을 만들고 그 배열을 reduce로 돌리면서 N번의 탐색을 개시했다.
당연히 결과는 시간초과가 나왔다…

그렇다면 어떻게 이번에 뛸 음수랑 다음에 건너뛸 음수의 경우간의 max를 비교할 수 있을까?..
한참 생각해도 시간초과를 통과할 방법이 생각이 안났는데, 다른 곳에서 힌트를 찾았다.
이제보니 너무 문제를 어렵게 생각했다.
잘 보면 수열에서 수를 하나 제거할 수 있다고 했다. 제거하지 않아도 되고 말이다.
그 뜻은 결과를 수를 제거한 경우와 수를 제거하지않은 경우 2가지다 끌고 가면 되는 뜻이였다.

즉, 표를 이렇게 만들어 풀면된다.

	10	-4	3	1	5	6	-35	12	21	-1
제거 안 한 경우	10	6	-	-	-	-	-	-	-	-
제거 한 경우	10	10	-	-	-	-	-	-	-	-

이 표를 이용하면 우리는 -4와 -35에서 어떻게 선택 할 건지 생각해봐야된다.
예를 들어 -4의 경우 제거를 안한 경우는 -4보다 10+(-4)가 크니깐 6이 될 것이고,
제거를 하는 경우는 제거를 한 10이 제거를 안한 10+(-4)보다 크니깐 10을 가져올 것이다.
그런데 이때 가져오는 10이란것은 제거 한 경우의 0번째 항의 10이 아니라 제거를 안 한 경우의 10이다.
왜냐? 제거를 한다고 치면 당연히 그 이전까지는 제거를 안했어야 한다. 그러므로 i-1번째까지 제거를 안 한 경우의 max값을 가져와야 하는게 맞다.

	10	-4	3	1	5	6	-35	12	21	-1
제거 안 한 경우	10	6	9	10	15	21	-14	12	33	32
제거 한 경우	10	10	13	14	19	25	21	33	54	33

이런 식으로 표가 나오게된다.
여기서 음수마다 [제거 한 경우]의 i번째 항은 [제거 안 한 경우]의 i-1번재 항의 값을 가져와 건너뛰었음을 알 수 있다.

그리고 당연히 결과물이 2가지가 되었으니 max값도 각 i번재 마다 제거를 안 한 경우와 제거를 한 경우를 2가지와 기존의 max값을 비교해서 저장하여 최종적인 max값을 반환해주면 된다.

정답 코드

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 answer = '';
  let n = input[0];
  let arr = input[1]
  arr = arr.split(' ')  
  answer = continuity_sum(n, arr);
  
  console.log(answer)
  process.exit();
});

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