We can design an improved algorithm

We can design an improved algorithm for the maximum subarray problem by observing
that we are wasting a lot of time by recomputing all the subarray summations
from scratch in the inner loop of the MaxsubSlow algorithm. There is
a much more efficient way to calculate these summations. The crucial insight is
to consider all the prefix sums, which are the sums of the first t integers in A for
t = 1, 2,...,n. That is, consider each prefix sum, St, which is defined as