최대 연속합
실버 II의견: 0
정수 수열 \(A_1, A_2, \dots, A_N\)이 주어진다.
이 수열에서 연속한 부분 수열을 하나 골라 그 합을 최대로 만들고 싶다. 부분 수열은 원래 수열에서 이어진 구간 \(A_l, A_{l+1}, \dots, A_r\) (\(l \le r\))이어야 하며, 적어도 하나의 수를 포함해야 한다.
가능한 최대 합을 구하여라.
수열의 모든 수가 음수일 수도 있다는 점에 주의하라. 그 경우에도 수를 하나는 골라야 하므로 답이 음수가 된다.
\(1 \le N \le 100\,000\), \(-10^9 \le A_i \le 10^9\).
첫째 줄에 수열의 길이 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(A_1, \dots, A_N\)이 공백으로 구분되어 주어진다.
연속한 부분 수열의 합 중 최댓값을 한 줄에 출력한다.
10
10 -4 3 1 5 6 -35 12 21 -1
33
\(12 + 21 = 33\)이 최대이다. 구간 \([10, -4, 3, 1, 5, 6]\)의 합은 \(21\)로 그보다 작다.
5
-2 -5 -1 -8 -3
-1
모든 수가 음수이므로 가장 큰 수 하나(\(-1\))만 고르는 것이 최선이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
최대 연속합
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최대 연속합