달콤한 구간
실버 V의견: 0
사탕 가게 주인 라라는 \(N\)개의 사탕이 일렬로 놓인 진열대에서 연속한 \(K\)개의 사탕을 하나의 봉지에 담아 팔려고 한다. 각 사탕에는 맛 점수가 적혀 있고, 음수인 사탕도 있다. (맛 점수가 낮은 사탕은 쓴맛이 나서 전체 점수를 깎는다.)
봉지에 담긴 사탕의 맛 점수 합이 최대가 되도록 \(K\)개를 골랐을 때, 그 합을 구하여라.
- \(1 \le K \le N \le 200\,000\)
- \(-10^9 \le\) 각 사탕의 맛 점수 \(\le 10^9\)
첫째 줄에 사탕의 수 \(N\)과 봉지 크기 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 각 사탕의 맛 점수 \(N\)개가 공백으로 구분되어 주어진다.
연속한 \(K\)개의 사탕 맛 점수 합의 최댓값을 출력한다.
7 3
1 7 3 5 2 8 4
15
길이 \(3\)인 모든 구간의 합은 \(1+7+3=11\), \(7+3+5=15\), \(3+5+2=10\), \(5+2+8=15\), \(2+8+4=14\)이다. 최대는 \(15\)이다. (구간 \([7,3,5]\) 또는 \([5,2,8]\))
8 4
-3 -1 -4 -1 -5 -9 -2 -6
-9
음수만 있는 배열이다. 길이 \(4\) 구간 합의 최대는 \(-3+(-1)+(-4)+(-1)=-9\)인 구간 \([-3,-1,-4,-1]\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
달콤한 구간
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
달콤한 구간