Informatica Online Judge

  maximum sum of maximum sum [1586 / 0632]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 24   Total Tried : 35


The Champion of this Problem (C++) : gs16051 - ms / 382byte
My Best Submission (C++) : N/A

[koistudy.net (15073 윤준성)]

Background

n개의 원소로 이루어진 집합이 있다.
부분합이란 n개의 원소중 i번째 원소로 부터 j번째 원소까지의 연속적인 합을 의미한다. (단, 1 <= i <= j <= n )

만약 다음과 같이 6개의 원소로 이루어진 집합이 있다고 가정하자.
6 -7 3 -1 5 2
이 집합에서 만들어지는 부분합 중 최대값은 3번째 원소부터 6번째 원소까지의 합인 9이다.

여기까지는 koistudy에 있는 Maximum sum 문제이다.
이 문제를 읽은 준성이는 여기서 만족하지 못하고 교집합이 없는 두 부분집합의 부분합을 구하여 그 두 부분합의 합을 최대로 만들려고 한다.
예를 들어 위의 예시인 6 -7 3 -1 5 2 에서 두 부분합의 최댓값은
( 6 ) + ( 3 - 1 + 5 + 2 ) = 15 이다.

각 부분집합은 적어도 하나의 원소를 가져야하며 두 집합 사이에는 적어도 하나의 원소가 있어야 한다.
자, 이제 교집합이 없는 두 집합의 부분합의 합의 최댓값을 구해보자.

Input

첫 줄에 원소의 수를 의미하는 정수 n 이 입력되고, 둘째 줄에 n개의 정수가 공백으로 구분되어 입력된다.


[입력값의 정의역]

3 <= n <= 100000
-1000 <= 각 원소의 크기 <= 1000

Output

주어진 집합에서 얻을 수 있는 교집합이 없는 두 집합의 부분합의 합의 최댓값을 출력한다.

IO Example

입력
6
6 -7 3 -1 5 2

출력
15

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]