3172 : 연속 부분 배열 최대합

시간 1.000s · 메모리 256MB · 제출 3 · 정답 2

코드제출 문제 풀기

채점기록 통계 묻고답하기

정수로 이루어진 수열이 주어질 때, 연속된 하나 이상의 원소를 선택하여 얻을 수 있는 원소들의 합 중 가장 큰 값을 구하는 프로그램을 작성하세요.

이때, 선택하는 원소들은 배열 상에서 중간을 건너뛰지 않고 연속해 있어야 하며, 최소 1개 이상의 수를 반드시 선택해야 합니다. (모든 수가 음수인 경우 가장 큰 음수 1개를 선택하게 됩니다.)

[제약 조건]
• $1 \le N \le 100{,}000$
• $-10{,}000 \le (\text{각 정수}) \le 10{,}000$
• 입력되는 모든 값은 정수입니다.

첫째 줄에 $N$이 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다.

연속된 부분 배열의 최대 합을 출력하세요.

8
-2 1 -3 4 -1 2 1 -5

예제에서 연속된 원소 4, -1, 2, 1을 선택했을 때 합이 6으로 최대가 됩니다.