문제
n개의 원소로 이루어진 집합이 있다.
이 집합에서 최대로 가능한 부분합을 구하는 것이 문제이다.
부분합이란 n개의 원소 중 i번째 원소로부터 j번째 원소까지의 연속적인 합을 의미한다.
(단, 1 <= i <= j <= n)
만약 다음과 같이 6개의 원소로 이루어진 집합이 있다고 가정하자.
6 -7 3 -1 5 2
이 집합에서 만들어지는 부분합 중 최댓값은 3번째 원소부터 6번째 원소까지의 합인 9이다.
입력
첫 줄에 원소의 수를 의미하는 정수 n이 입력되고,
둘째 줄에 n개의 정수가 공백으로 구분되어 입력된다.
(단, 2 <= n <= 100,000; 각 원소의 크기는 -1000에서 1000 사이의 정수이다.)
출력
이 집합에서 나올 수 있는 부분합 중의 최댓값을 출력한다.
예제
6
6 -7 3 -1 5 2
9
출처
문제해결을 위한 창의적 알고리즘 (고급), comkiwer
로그인해야 코드를 작성할 수 있어요.