최대 연속 부분합
면접 대비시간 제한1초메모리 제한128 MB
최대 100,000개의 정수가 주어질 때 연속된 부분 배열 중 합이 최대인 값을 구하는 문제입니다.
문제
정수 n개로 이루어진 수열이 주어진다. 이 수열에서 하나 이상의 연속한 원소를 선택했을 때 만들 수 있는 합의 최댓값을 구하라.
입력
첫째 줄에 정수 n (1 ≤ n ≤ 100,000)이 주어진다.
둘째 줄에는 n개의 정수가 공백으로 구분되어 주어진다. 각 정수는 -1,000 이상 1,000 이하이다.
출력
하나 이상의 연속한 원소를 선택해 얻을 수 있는 합의 최댓값을 출력한다.