Maximum Subarray Problem

For subtask $1$, compute the sum of every interval $(l,r)$ from scratch in $O(N^3)$ time.

For subtask $2$, compute prefix sums $P_i=A_1+\cdots+A_i$. Each interval sum is $P_r-P_{l-1}$, giving $O(N^2)$ time.

For the full problem, let $D_i$ be the maximum sum of a nonempty subarray ending at $i$. We can either take only the last element or append $A_i$ to the best subarray ending at $i-1$. Hence

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

The answer is the maximum of all $D_i$. Initialize with $A_1$ rather than $0$ to handle arrays containing only negative values. A sum can exceed the range of a $32$-bit integer, so use a $64$-bit integer.

The full solution uses $O(N)$ time and $O(1)$ extra space.

Solution written by GPT6