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보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

====

문제 분석

인덱스가 최대 10만이므로 시간 복잡도는 N을 지향해야한다.

이 문제에서 특이점은 연속된 수 중 뺴고 싶은 것이 생긴다면 하나는 뺄 수 있다는 것이다.

만약 이러한 특이점이 없다면 dp를 선언 후 각 인덱스 별로 dp[i]= MAX(dp[i-1]+arr[i] , arr[i]) 라는 점화식을 사용하면 된다.

그렇다면 하나를 뺄 수 있다는 특이점을 사용할려면 

(이전까지 하나도 빼지않고 연속 된 수를 만든 것중 합이 제일 큰 값)과 (이전까지 한번은 빼고 온 연속 된 수를 만든 것 중 합이 제일 큰 값에 arr[i] 를 더한 값)을 비교하면 된다.

1. 이전까지 하나도 빼지 않았다는 것은 이번의 수는 뺄 수 있는 것므로 이전까지의 합을 그대로 가져오면 되고

2. 이전까지 한번은 빼고 온 연속 된 수를 만든 것 중 합은 이제는 뺄 수 있는 것이 아니므로 그 수에 현재 arr[i]를 무조건 더해야 하는 것이다.

dp 자체를 2개의 행으로 만들어서 첫번째 행에는 연속 된 수 중 한 번도 뺀 적이 없이 만든 제일 큰 합을 기록

두번째 행에는 연속된 수 중 중간에 하나는 제외하고 더한 제일 큰 합을 기록한다.

const dp = Array.from({ length: 2 }, () =>
        Array.from({ length: n }, () => 0)
    );

    dp[0][0] = arr[0];
    dp[1][0] = arr[0];

위에서 만든 것을 점화식으로 표현하면

dp[0][i] = Math.max(dp[0][i - 1] + arr[i], arr[i]);
dp[1][i] = Math.max(dp[0][i - 1], dp[1][i - 1] + arr[i]);

정답 코드

const main = (n, arr) => {
    const dp = Array.from({ length: 2 }, () =>
        Array.from({ length: n }, () => 0)
    );

    dp[0][0] = arr[0];
    dp[1][0] = arr[0];

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

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const arr = input[1].split(' ').map((v) => +v);
main(n, arr);