Testing

Several sets of test data were used to ensure the accuracy of each of the algorithms. These test data were comprised of arrays of values with known maximum sub-array solutions. These test sets were run through each algorithm, and the output was compared to the known solution.

Along with the provided set of test cases, several additional test cases were generated in order to test the algorithm accuracy under very specific conditions. Some examples of these test cases include:

  • The trivial case of a single array element
  • Arrays with a single positive value as the first or last element (to test the handling of the boundaries)
  • Arrays with a single positive value in the middle of the arrary
  • Arrays where the running sum reaches 0 at some point (i.e. multiple maximum sum sub-arrays possible)

All algorithms correctly solved all of the test data sets.

Algorithm Comparison Plots

Three plots were generated with various combinations of linear and log scales to show the performance of the various algorithms together.

Linear plot:

Linear Log plot:

Log Log plot: