[node.js,백준]13398 - 연속합 2

목차

 

 

 문제

링크

https://www.acmicpc.net/problem/13398

문제

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

 

출력

첫째 줄에 답을 출력한다.

 

주저리

연속합 문제의 2번째 문제로

연속된 몇개의수를 선택해서 구할수있는 가장 큰합을 구하는 문제이다.

단, 수는 한개 이상 선택해야하며

수열에수 수를 하나 제거하거나 제거하지 않아도된다.

해당문제를 구하기위해

연속된 합을 구하는 testF함수를 만들었고

수를제거할수있다라는 조건때문에

찾고자하는 부분(=i) 를 기준으로

i-1번째의 부분합과 i+1의 부분합을 구한후

첫번째랑 마지막과 나머지에대한 분기처리를해서

찾는부분을 제외한 합이랑, 합한 합, 음수일땐 자기자신, 그리고 이전 최대합의 max를 통해 구했다.

 

풀이

 입력처리

• 표준 입력 또는 테스트 데이터를 사용하여 input 변수에 할당합니다.
• input을 처리하여 real 배열에 저장합니다.

 testF 함수

• 이 함수는 주어진 배열을 사용하여 각 위치에서의 최대 연속 부분합을 계산합니다.
• 첫 번째 요소는 배열의 첫 번째 값으로 초기화됩니다.
• 배열의 나머지 요소들에 대해서 이전 연속합에 현재 값을 더한 것과 현재 값을 비교하여 더 큰 값을 선택합니다.

 solution 함수

• real 배열로부터 전체 원소의 수 T와 실제 수열 rest를 추출합니다.
• 만약 배열의 크기가 1이면, 유일한 원소를 출력하고 종료합니다.
• testF 함수를 두 번 호출하여, 한 번은 원래 배열에 대해, 다른 한 번은 배열을 뒤집어서 계산합니다.
• 두 배열(arrs, arrs_reverse)에서 계산된 결과를 사용하여 가능한 최대 값을 찾습니다. 각 위치에서 가능한 경우는 다음과 같습니다:
  • 현재 위치를 제외한 왼쪽의 최대 연속합
  • 현재 위치를 제외한 오른쪽의 최대 연속합
  • 현재 위치의 값 자체
  • 현재 위치를 포함한 좌우의 합

 결과 출력

• 계산된 최대값 maxes를 출력합니다.

 코드

 

// 연속합 2
var fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString();

let real = input.trim().split("\n");
let arrs = [];
let arrs_reverse = [];
let Vs = [];
function testF(N, rest, arrays) {
    // for (let i = 0; i < 1; i++) arrs[0][i] = 1;

    for (let i = 0; i < N; i++) {
        // let reArr = [];
        if (i === 0) {
            arrays[i] = rest[0];
        }
        else {
            let target = rest[i];
            let sum = arrays[i - 1] + target;
            // console.log({ target, sum }, Math.max(target, sum));
            if (target === sum) {
                arrays[i] = sum;
            }
            if (sum === Math.max(target, sum)) {
                arrays[i] = sum;
            } else {
                arrays[i] = target;
            }
        }
        // arrs.push(reArr);
    }
}


function solution(real) {
    let [T, sec] = real;
    let rest = sec.split(" ").map(Number);
    if (Number(T) === 1) {
        console.log(rest[0])
        return;
    }
    let restReverse = [...rest].reverse();
    testF(Number(T), rest, arrs)
    testF(Number(T), restReverse, arrs_reverse)
    arrs_reverse.reverse();
    // console.log(arrs);
    // console.log(arrs_reverse);
    let maxes = -Infinity;
    for (let i = 0; i < arrs.length; i++) {
        let t1;
        if (i === 0) {
            t1 = arrs_reverse[i + 1];
        }
        else if (i === arrs.length - 1) {
            t1 = arrs[i - 1];
        }
        else {
            t1 = arrs[i - 1] + arrs_reverse[i + 1]
        }

        // console.log({ t1 })
        maxes = Math.max(t1, t1 + rest[i], rest[i], maxes);
    }
    console.log(maxes);

}
solution(real);