연속합 2147483647
면접 대비시간 제한2초메모리 제한512 MB
n개의 정수 수열이 주어질 때, 적어도 하나의 수를 포함하는 연속한 부분 수열의 합 중 최댓값을 구한다.
문제
n개의 정수로 이루어진 수열이 주어진다. 이 수열에서 연속된 몇 개의 수를 골라 합을 구할 때, 그 합의 최댓값을 구하려고 한다. 수는 한 개 이상 골라야 한다.
예를 들어 수열 10, -4, 3, 1, 5, 6, -35, 12, 21, -1이 주어졌다면, 12 + 21 = 33이 정답이 된다.
입력
첫째 줄에 자연수 n이 주어진다.
둘째 줄에 수열을 이루는 n개의 정수 ai가 공백을 사이에 두고 주어진다.
출력
첫째 줄에 답을 출력한다.
제한
- 1 ≤ n ≤ 300,000
- -1,000,000,000 ≤ ai ≤ 1,000,000,000 (단, 서브태스크 11은 예외)
힌트
이 문제를 풀었을 때의 점수는 다음과 같이 계산한다.
- (맞은 서브태스크의 배점의 총합 + X) mod 2147483648
- X = 328 (기본 점수)