문제
N개의 정수가 주어질 때, 연속된 부분을 선택하여 합을 최대화 하는 프로그램을 작성하시오. 예를 들어, 아래와 같이 8개의 숫자가 있을 경우, 색칠된 부분을 선택했을 때 그 합이 가장 최대가 된다.
입력
첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두 번째 줄에 n개의 정수가 주어진다.
출력
연속된 부분을 선택하였을 때의 최댓값을 출력한다.
예제 입력
8
2 3 -5 8 -3 4 2 -9
예제 출력
11
예제 입력
5
-1 -2 3 -2 4
예제 출력
5
주어진 숫자들 중에서 연속부분의 최대합을 구하는 문제이다. 완전탐색을 해서 범위를 점점 늘리거나 줄여가면서 구하면 쉽게 구할 수 있는 문제이지만, 입력을 보면 범위가 100,000 까지 이기 때문에, 완전탐색으로 시간복잡도가 
1) 중간값(mid)를 잡아서 왼쪽부분과 오른쪽 부분으로 나눈다.
2) 왼쪽부분에서 연속부분의 최대합을 구하고, 오른쪽부분에서 연속부분의 최대합을 구한다.
3) 그러면 문제는, 중간값(mid)를 포함한 부분 연속부분 최대합을 빼고 구한것인데, 이부분에서 중간값을 기준으로 왼쪽과 오른쪽을 독립적으로 봐서 왼쪽에서 연속부분최대합을 구하고, 오른쪽에서 연속부분최대합을 구한 후 더하면 중간값을 포함한 연속부분최대합이 나오게 된다.
위의 사진을 보면 더 쉽게 이해가 되는데, 중간값을 기준으로 왼쪽과 오른쪽부분에서 나올 수 있는 최대값을 모두 적은것이다. 왼쪽과 오른쪽을 독립적으로 본다는 말은 결국 우리가 구하는 것은 mid 를 포함한 범위중 최대값을 구해야 하는 것인데, mid 의 왼쪽에서 최대값이 나오는 범위와 mid 의 오른쪽에서 최대값이 나오는 범위를 더하면 mid 를 포함한 최대값이 나온다는 것이다.
4) mid의 왼쪽, mid의 오른쪽, mid를 포함한 연속부분최대합을 구해서, 3개중에 가장 큰 범위가 답이 된다.
5) T(N) 을 N개의 숫자중 연속부분최대합을 구하는 시간이라고 하면 mid 의 왼쪽부분에서 T(N/2), 오른쪽부분에서 T(N/2), 마지막으로 mid를 포함한 연속부분최대합을 구하는 시간은 O(N) 이기 때문에, T(N) = 2T(N/2) + O(N) 이라는 식을 얻을 수 있고, 결국
