Informatica Online Judge

  부동산 투자 [1110 / 0456]

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


The Champion of this Problem (C++) : icp1481 - 0ms / 474byte
My Best Submission (C++) : N/A

[koistudy.net (T. JK Jeong 2014)]

Background

경곽이는 부동산 투자에 대한 설명을 듣고 라인월드의 땅을 사기로 했다.

라인월드는 직선형으로 이루어져 있으며 n개의 영역으로 구성되며, 각 영역의 땅 값이 -1,000 ~ 1,000 까지의 가치를 지닌다.

음수는 이 땅을 사면 손해본다는 의미이다. 당연히 값이 클 수록 이익이 큰 땅이다.

경곽이는 a번 땅부터 b번 땅까지 연속된 땅을 얻어갈 수 있다. (단, 1 <= a <= b <= n )

그리고 경곽이는 조금 더 욕심을 내어 연속된 영역을 하나 더 얻어갈 수도 있다.

즉 경곽이가 살 수 있는 땅은 구간 [a, b] 와 [c, d]의 두 구간을 얻을 수도 있다.
(단, 1 <= a <= b <= n ; b < c <= d <= n )

정리하면 경곽이는 연속된 땅을 1구간 또는 2구간을 가져갈 수 있을 때 경곽이가 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 영역의 크기 n이 입력된다.
두 번째 줄에는 n개의 각 영역의 가치가 입력된다.

[Sub-Task Info]
- 입력데이터의 18%는 n <= 10 을 만족한다.
- 입력데이터의 12%는 n <= 100 을 만족한다.
- 입력데이터의 16%는 n <= 3,000 을 만족한다.
- 입력데이터의 54%는 n <= 300,000 을 만족한다.

Output

경곽이가 얻을 수 있는 최대 이익을 출력한다.

IO Example

입력
5
1 2 3 4 5

출력
15

입력2
4
3 -2 -1 4

출력2
7

* 설명 : 입력1의 경우에는 1번 땅부터 5번 땅까지 1개의 영역을 얻어가는 것이 가장 이익이다. 입력2의 경우에는 1번 땅과 4번 땅의 2개의 영역을 얻어가는 것이 가장 이익이다.

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