#!/usr/bin/python3
"""Understanding Kadane’s algorithm for the maximum subarray problem.

This finds the subarray of a given array of signed numbers with the
greatest sum.  In linear time, it magically picks the maximal one of
all the N(N+1)/2 subarrays.  This version is allowed to pick empty
subarrays.

The underlying insight here is that all the subarray totals ending at
a given point, except for one, are related in the same way to the
subarray totals ending at the previous point; they differ by the
value of that point.  So if, say, sum(f[4:6]) > sum(f[3:6]), then
sum(f[4:7]) > sum(f[3:7]), in fact by exactly the same amount.  The
one exception is the empty subarray, f[7:7], which sums to 0.

So at each point, we only need to consider two candidate maximum
subarrays that end at that point, one of which is empty.

(Codility calls it the “maximum slice problem” and doesn’t credit
Kadane.)

This ``gms`` function puts the execution trace of all the function’s
variables into rows of a Numpy array to help me understand what’s
going on in the algorithm.  For example:

    In [50]: maxslice.gms([1, -2, 3, -4, 5, -6, 7, 7])
    Out[50]: 
    array([[ 1, -2,  3, -4,  5, -6,  7,  7],
           [ 1,  0,  3,  0,  5,  0,  7, 14],
           [ 0,  2,  2,  4,  4,  6,  6,  6],
           [ 1,  1,  3,  3,  5,  5,  7, 14],
           [ 0,  0,  2,  2,  4,  4,  6,  6],
           [ 1,  1,  3,  3,  5,  5,  7,  8]])

Probably a Pandas dataframe would be better, since it would allow you
to label things.

"""
import numpy


def gms(ns):
    max_endings = [0]
    max_slices = [0]
    start_indices = [0]
    best_starts = [0]
    best_ends = [0]
    for i, n in enumerate(ns):
        nc = max_endings[-1] + n
        if nc > 0:
            max_endings.append(nc)
            start_indices.append(start_indices[-1])
        else:
            max_endings.append(0)
            start_indices.append(i+1)

        if max_endings[-1] > max_slices[-1]:
            max_slices.append(max_endings[-1])
            best_starts.append(start_indices[-1])
            best_ends.append(i+1)
        else:
            max_slices.append(max_slices[-1])
            best_starts.append(best_starts[-1])
            best_ends.append(best_ends[-1])

    return numpy.array([ns,
                        max_endings[1:],
                        start_indices[1:],
                        max_slices[1:],
                        best_starts[1:],
                        best_ends[1:]])