7033 : 최대 연속 부분합
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 리스트가 주어집니다. 이 리스트에서 하나 이상의 연속된 원소들을 선택했을 때, 그 원소들의 합이 최대가 되는 경우의 합(최대 연속 부분합)을 구하는 프로그램을 작성하십시오.
예를 들어, 리스트가
[제약 조건]
• 리스트 크기 $N$: $1 \le N \le 5{,}000$
• 각 정수 원소: $-10^6 \le a_i \le 10^6$
예를 들어, 리스트가
[1, -2, 3, 4, -5] 라면 연속 부분 배열 [3, 4]를 골랐을 때 합이 $7$로 최대가 됩니다.[제약 조건]
• 리스트 크기 $N$: $1 \le N \le 5{,}000$
• 각 정수 원소: $-10^6 \le a_i \le 10^6$
입력 설명
첫째 줄에 리스트의 크기 $N$ ($1 \le N \le 5000$)이 주어집니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. 각 정수는 $-10^6$ 이상 $10^6$ 이하입니다.
둘째 줄에 $N$개의 정수가 공백으로 구분되어 주어집니다. 각 정수는 $-10^6$ 이상 $10^6$ 이하입니다.
출력 설명
리스트에서 얻을 수 있는 최대 연속 부분합을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
1 -2 3 4 -5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
7도움
이중 반복문을 돌려 모든 연속 구간의 합을 브루트포스로 구할 수도 있지만($O(N^2)$), 동적 계획법인 카데인 알고리즘(Kadane's Algorithm)을 활용하면 $O(N)$의 시간 복잡도로 빠르게 구할 수 있습니다.
dp[i] = max(arr[i], dp[i-1] + arr[i])를 사용합니다.