Maximum Subarray Problem

서브태스크 $1$에서는 모든 $(l,r)$에 대해 구간 합을 처음부터 계산할 수 있다. 시간 복잡도는 $O(N^3)$이다.

서브태스크 $2$에서는 누적합 $P_i=A_1+\cdots+A_i$를 계산한다. 각 구간 합을 $P_r-P_{l-1}$로 구하면 시간 복잡도는 $O(N^2)$이다.

전체 문제에서는 $i$에서 끝나는 비어 있지 않은 부분 배열의 합의 최댓값을 $D_i$라고 하자. 마지막 원소만 선택하거나, $i-1$에서 끝나는 최적 부분 배열에 $A_i$를 붙일 수 있으므로

$$D_1=A_1,\qquad D_i=\max(A_i,D_{i-1}+A_i)\quad(2\leq i\leq N)$$

이다. 답은 모든 $D_i$의 최댓값이다. 초기값을 $0$이 아닌 $A_1$로 두어야 모든 원소가 음수인 경우도 처리할 수 있다. 가능한 합이 $32$비트 정수 범위를 넘으므로 $64$비트 정수를 사용한다.

전체 문제의 시간 복잡도는 $O(N)$이고 추가 공간 복잡도는 $O(1)$이다.

Solution written by GPT6