구간 최대 부분합
플래티넘 V의견: 0
마법 연구소에는 \(N\)개의 마나 수치 \(A_1, A_2, \dots, A_N\)이 기록되어 있다. 각 수치는 양수 또는 음수일 수 있다.
연구원들은 \(Q\)개의 질문을 한다. 각 질문은 두 정수 \(l\), \(r\)로 이루어지며, 배열의 \(l\)번째부터 \(r\)번째 원소로 이루어진 부분 배열 \(A_l, A_{l+1}, \dots, A_r\) 에서 연속 부분합의 최댓값을 묻는다. 연속 부분합은 반드시 한 개 이상의 원소를 포함해야 한다.
각 질문에 답하여라.
- \(1 \le N \le 200\,000\)
- \(1 \le Q \le 100\,000\)
- \(-10^9 \le A_i \le 10^9\)
- \(1 \le l \le r \le N\)
첫째 줄에 배열의 크기 \(N\)과 질문의 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 배열 원소 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 질문 \(l\), \(r\)이 공백으로 구분되어 주어진다 (\(1 \le l \le r \le N\)).
\(Q\)개의 줄에 걸쳐 각 질문에 대한 연속 부분합의 최댓값을 순서대로 출력한다.
9 2
-2 1 -3 4 -1 2 1 -5 4
1 9
1 4
6
4
구간 \([1,9]\) 전체에서 최대 연속 합은 \([4,-1,2,1]=6\)이다. 구간 \([1,4]\)에서는 \(4\)가 최대다.
6 2
2 -1 2 3 -9 2
1 6
5 6
6
2
구간 \([1,6]\) 전체의 최대 연속 합은 \([2,-1,2,3]=6\)이다. 구간 \([5,6]\)에서는 \([-9,2]\) 중 \(2\)가 최대다.
riseoj 작성
출처 Original
평가 및 의견
구간 최대 부분합
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
구간 최대 부분합