\chapter{Finding the Maximum Subarray Sum}
The objective of this challenge is to find the maximum value of the sum of
elements in a subarray of a given array. If all integers are negative, said
maximum value is the sum of a subarray equivalent to the `empty set', which is
zero.

\section{Cubic Brute Force Algorithm}
\imb[6][15]{\alg/maxsubarray.cpp}
This algorithm utilises three loops and a function of constant time in the
innermost loop. Therefore, the time complexity analysis goes:
\[ T(n)=\sum_{i=1}^n\sum_{j=i}^n\sum_{k=i}^j1=O\left(n^3\right) \]
Obviously this method is quite wasteful in both memory and timekeeping. The
following two algorithms are substantial progessions from this algorithm:
\newpage

\section{Quadratic Brute Force Algorithm}
\imb[18][27]{\alg/maxsubarray.cpp}
This algorithm utilises two loops and a function of constant time in the
innermost loop. Therefore, the time complexity analysis goes:
\[ T(n)=\sum_{i=1}^n\sum_{j=i}^n1=O\left(n^2\right) \]

\section{Divide and Conquer}
\imb[30][49]{\alg/maxsubarray.cpp}
This algorithm utilises a divisive recursion and selection controls of constant
time within each recursion. Therefore, the time complexity analysis goes:
\[ T(n)=2T\left(\frac{n}{2}\right)+n=2^kT\left(\frac{n}{2^k}\right)+nk,~
\therefore T(n)=2^{\log_2n}T(1)+n\log_2n=n\log_2n+\varepsilon n=O(n\log n) \]
\newpage
While these two algorithms are quite effective compared to Cubic Brute Force,
this last algorithm manages to provide the fastest solution possible:

\section{Kadane's Algorithm: A Linear, Incremental Solution}
\imb[52][59]{\alg/maxsubarray.cpp}
This algorithm utilises one loop and a function of constant time in the loop.
Therefore, the time complexity analysis goes: \[ T(n)=\sum_{i=1}^n1=O(n) \]

Since, essentially, the challenge requires a system to read each data at least
once, the $O(n)$ function above is obviously the best solution.
