Max slice explained

max_slice.py

# starting array
A = [5, -2, 10, 3, -25, 12, 6]
# calculating the max slice in O(n), starting from A[1]
# copy A into S, where the max slices are stored
S = A[:]
# instead of looping, I'll unroll the loop for simplicity
# so, at S[1], we either add the previous sum, or start over
# to decide that, we simply check the max between the element and the previous sum added
S[1] = max(S[1], S[1] + S[0])
# S = [5, 3, ...]
S[2] = max(S[2], S[2] + S[1])
# S = [5, 3, 13, ...]
# S = [5, 3, 13, 16, ...]
# S = [5, 3, 13, 16, -9, ...]
# S = [5, 3, 13, 16, -9, 12, ...]
# S = [5, 3, 13, 16, -9, 12, 18]
# answer = max(S)