소프티어

풀이 과정 포함 (밑에 주석)

const fs = require('fs');
const input = fs.readFileSync('input.txt', 'utf8').trim().split(/\n+/)[1].split(' ').map(Number);

const array1 = [...input].fill(0)
const array2 = [...input].fill(0)
let first = true
function dp(acc, cur, idx, array) {
    array[idx] = Math.max(acc + (first ? cur : 0), cur)
    return array[idx]
}

// 1,2,3,4 단계
input.reduce((acc, cur, idx) => dp(acc, cur, idx, array1), 0)
input.reverse().reduce((acc, cur, idx) => dp(acc, cur, idx, array2), 0)

// 5 단계
first = false
array1.reduce((acc, cur, idx) => dp(acc, cur, idx, array1), Number.MIN_SAFE_INTEGER)
array2.reduce((acc, cur, idx) => dp(acc, cur, idx, array2), Number.MIN_SAFE_INTEGER)
array2.reverse()

// 6 단계
let answer = Number.MIN_SAFE_INTEGER;
const n = input.length;
for (let i = 0; i < n - 2; i++) {
    answer = Math.max(answer, array1[i] + array2[i+2]);
}
console.log(answer);


/*
배열 순회

1. 배열 읽기 (L -> R)
2. 현재 값을 부분 집합에 추가하는 것 보다 새로 부분집합을 시작하는 것이 값이 더 크면 -> 새로운 부분 집합(요리) 시작
3. 새 배열에 항상 max를 저장
4. 최종적으로 배열에는 각 부분집합들의 L->R 순차적인 합들이 기록됨
5. 이제 특정 index 기준 왼쪽에 있는 값들 중 최대로 다 채우기 ([2]가 4이고 [3]이 2이면 [3]포함 왼쪽에는 4라는 요리의 합이 존재한다는 것을 알려주는 것 DP)
6. 그러면 이제 그냥 배열 순회하면서 i i+2를 합하면서 최대만 찾으면 됨.
 */

오랜만에 알고리즘 해보니 머리가 안돌아가요