문제

• 
• 시간 제한: 2초
• 메모리 제한: 128MB

Problem Analysis

가능한 양 끝 i,j의 모든 경우는 n(n+1)/2 가지이다. 대신에, Divide and Conquer로, 좌우로 분할하여 각 구간에서 최대를 찾고, 구간을 합칠 때 경계선에서 만들어지는 경우만 조사하면, 시간 복잡도를 개선할 수 있을 것이다.

Algorithm

(l, r)에서의 최대를 다음과 같이 divide and conquer로 구한다.
1. l, mid에서의 최대를 구한다.
2. mid+1, r에서의 최대를 구한다.
3. 경계선을 반드시 포함하는 경우의 최대를 구한다.
4. 위의 세 가지 중에서 최대를 return 한다.

이때 3번을 구할 때,
(mid, mid) 에서 시작하여, 매번 좌와 우중 최적의 방향으로 한칸씩 늘려 (l, r)까지 조사한 값 중에서. 이는 시간복잡도가 O(N)이다.

Data Structure

• arr[]: 수 저장

결과

Other

시간 복잡도는 T(n) = 2*T(2/n) + O(n)이므로 O(nlogn)이다.
이때, 수의 범위가 크기 때문에 무조건 모든 연산에 int64_t를 사용한다.