길이 제한 최대 구간 합
실버 I의견: 0
주식 분석가 민준이는 \(N\)일간의 일별 손익 기록을 가지고 있다. 민준이는 연속된 날의 손익 합이 최대가 되는 투자 구간을 찾고 싶다. 단, 투자 기간은 \(L\)일 이상 \(R\)일 이하여야 한다.
정확히 말하면, 길이가 \(L\) 이상 \(R\) 이하인 연속 부분 수열의 합의 최댓값을 구하여라.
- \(1 \le L \le R \le N \le 200\,000\)
- \(-10^9 \le a_i \le 10^9\)
첫째 줄에 일수 \(N\), 최소 기간 \(L\), 최대 기간 \(R\)이 공백으로 구분되어 주어진다.
둘째 줄에 \(N\)일간의 일별 손익 \(a_1, a_2, \dots, a_N\)이 공백으로 구분되어 주어진다.
길이가 \(L\) 이상 \(R\) 이하인 연속 부분 수열의 합의 최댓값을 출력한다.
6 2 4
1 -2 3 4 -1 2
8
길이 \(2\) 이상 \(4\) 이하의 모든 연속 부분 수열 중 합이 최대인 것을 찾는다. 구간 \([3, 4, -1, 2]\) (길이 \(4\))의 합은 \(8\)이고, 구간 \([3, 4]\) (길이 \(2\))의 합도 \(7\)이다. 최대 합은 \(8\)이다.
4 1 2
-1 -2 -3 -4
-1
모두 음수이므로 길이가 짧을수록 유리하다. 길이 \(1\) 구간 중 최댓값은 \(-1\)이다.
1 1 1
5
5
원소가 하나이므로 길이 \(1\) 구간 \([5]\)의 합 \(5\)가 답이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
길이 제한 최대 구간 합
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
길이 제한 최대 구간 합