Case study: Maximum Subarray

Example

Given $A=[10,-5,4,3,6,-1,-1]$ the subarray $A[\mathrm{1..6}]=[10,-5,4,3,-5,6]$ has sum $10+...+6=13$. It is the best we can do.

Convention. We can take $j=i-1$, so $A[i..j]isempty$, and the sume is zero.

Brute force algorithm

Runtime: $\Theta (n^3)$

Improved brute force algorithm Idea: we recompute the same sum many times in the $j$ loop.

Runtime: $\Theta (n^2)$

But we can do better. Let’s introduce the concept of Divide and Conquer

Idea: solve the problem twice in size $\frac{n}{2}$ (we assume $n$ is a power of 2). Then the optimal subarray (if not empty)

1. is completely in the left half $A[\mathrm{1..}n/2]$
2. or is completely in the right half $A[n/2+\mathrm{1..}n]$
3. or contains both $A[n/2]$ and $A[n/2+1]$ (cases mutually exclusive)