챌린지 » 최대 부분 배열의 합
최대 부분 배열의 합
문제
주어진 정수 배열에서 연속된 원소들의 합 중 가장 큰 값을 찾아내는 문제입니다.
입력 형식
- 첫 줄에 배열의 크기 N (1 <= N <= 10000)이 주어집니다.
- 두 번째 줄에 N개의 정수로 이루어진 배열이 주어집니다. (각 정수는 -10^6 <= arr[i] <= 10^6)
- 최대 부분 배열의 합을 출력합니다.
출력 형식
제약조건
1 <= N <= 10000 -10^6 <= arr[i] <= 10^6
예제
예제 1
입력
5 -2 1 -3 4 -1 2 1 -5 4
출력
6
설명
부분 배열 [4, -1, 2, 1]의 합이 6으로 최대입니다.
예제 2
입력
4 1 2 3 4
출력
10
설명
모든 원소를 포함하는 부분 배열의 합이 최대입니다.
힌트 보기
카데인 알고리즘(Kadane's Algorithm)을 사용해 보세요.
코드 작성
제출하려면 로그인이 필요합니다.