연습문제

효도 음식

난이도
Lv. 3
제출
698 명
참가자
232 명
정답률
33.95 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C 1초 1024MB
Java 2초 1024MB
Python 1초 1024MB
C++ 1초 1024MB
JavaScript 1초 1024MB

남우는 어버이날을 맞이하여 요리를 진행하려고 합니다. 요리는 2개를 만들려고 하고, 이를 위해 n 개의 재료를 준비했습니다.



재료를 1번부터 순서대로 n 번까지 나열했다 했을 때, 요리를 만들기 위해서는 다음 두 조건을 만족해야 합니다.


1. 요리는 연속한 재료들로만 만들 수 있습니다. 이때 최소 1개 이상의 재료를 선택해야만 합니다.

2. 서로 다른 요리에 사용되는 재료끼리 겹쳐서도, 그리고 인접해서도 안됩니다.


예로 [재료1, 재료2, 재료3, 재료4, 재료5] 이렇게 5개의 재료가 순서대로 주어졌을 때, ([재료2, 재료3]), ([재료4, 재료5]) 이렇게 재료를 선택하여 두 요리를 만들게 된다면 인접한 재료인 재료3, 재료4는 서로 다른 요리에 사용되므로 불가능한 선택지가 됩니다.


각 재료마다 부모님의 선호도가 정해져 있으며, 만족도는 두 요리에 쓰인 재료의 선호도의 총 합으로 정해집니다. 조건을 만족하며 두 요리를 통해 얻을 수 있는 최대 만족도를 구하는 프로그램을 작성해보세요.



본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.

제약조건

  • 3 ≤ n ≤ 100,000
  • -1,000 ≤ 선호도 ≤ 1,000

입력형식

첫 번째 줄에 n 이 주어집니다.

두 번째 줄에는 부모님의 선호도를 나타내는 n 개의 숫자가 공백을 사이에 두고 주어집니다.

출력형식

첫 번째 줄에 두 요리를 준비하여 얻을 수 있는 최대 만족도를 출력합니다.

입력예제1

6
4 -6 1 2 -2 3
출력예제1

8

[4], [1, 2, -2, 3] 이렇게 2개의 재료로 나눠 요리를 진행하면 만족도를 8만큼 얻을 수 있습니다.

입력예제2

3
-10 25 -10
출력예제2

-20

[-10], [-10] 이렇게 나눠야만 서로 다른 요리에 쓰인 재료끼리 인접하지 않고 요리를 2개 만들 수 있게 되므로 만족도는 -20이 됩니다.

목록