6072 : 연속된 수의 합 최대
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
연속된 수의 합 최대 (갱신 포함)
N개의 정수 배열에서 원소 갱신이 일어날 때마다 전체 배열의 최대 연속 부분합을 구하시오.
카데인(Kadane) 알고리즘으로 $O(N)$에 최대 연속 부분합을 계산할 수 있습니다.
출력 시점:
- 초기 배열 상태에서 1회
- 각 갱신 이후 1회씩
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 원소: $-10^4 \le a_i \le 10^4$ (정수)
N개의 정수 배열에서 원소 갱신이 일어날 때마다 전체 배열의 최대 연속 부분합을 구하시오.
카데인(Kadane) 알고리즘으로 $O(N)$에 최대 연속 부분합을 계산할 수 있습니다.
출력 시점:
- 초기 배열 상태에서 1회
- 각 갱신 이후 1회씩
[제약 조건]
• 배열 크기 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 원소: $-10^4 \le a_i \le 10^4$ (정수)
입력 설명
첫째 줄에 원소 개수 N (1 ≤ N ≤ 10,000)과 갱신 횟수 Q (1 ≤ Q ≤ 5,000)가 주어집니다.
둘째 줄에 N개의 정수가 주어집니다.
셋째 줄부터 Q개의 줄에 갱신 정보 i val (i번째 원소를 val로 변경)이 주어집니다.
둘째 줄에 N개의 정수가 주어집니다.
셋째 줄부터 Q개의 줄에 갱신 정보 i val (i번째 원소를 val로 변경)이 주어집니다.
출력 설명
초기 및 각 갱신 후의 최대 연속 부분합을 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 2
-2 1 -3 4 -1
2 10
4 -10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4
11
10