8011 : 최대 부분배열 합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 배열이 주어집니다.
이 배열의 비어 있지 않은 연속된 부분배열(Contiguous Subarray) 중 원소들의 합이 최대가 되는 부분배열의 합을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $-10^9 \le x_i \le 10^9$
이 배열의 비어 있지 않은 연속된 부분배열(Contiguous Subarray) 중 원소들의 합이 최대가 되는 부분배열의 합을 구하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $-10^9 \le x_i \le 10^9$
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
둘째 줄에 $N$개의 정수 $x_1, x_2, \ldots, x_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수 $x_1, x_2, \ldots, x_N$이 공백으로 구분되어 주어집니다.
출력 설명
연속된 부분배열의 합의 최댓값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
8
-1 3 -2 5 3 -5 2 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
9도움
카데인 알고리즘(Kadane's Algorithm)을 사용합니다.
현재 위치까지의 최대 부분합을 $O(N)$ 단일 순회로 갱신하며 전체 최댓값을 추적합니다.
모든 원소가 음수일 수 있으므로 초기 최댓값 설정에 주의하십시오.
현재 위치까지의 최대 부분합을 $O(N)$ 단일 순회로 갱신하며 전체 최댓값을 추적합니다.
모든 원소가 음수일 수 있으므로 초기 최댓값 설정에 주의하십시오.