How to solve maximum slice problems
So I looked at the question guide problem codility.com for maximum slice problems. And it says you can reduce the time complexity down from O(n^3) to O(n), using smart algorithms. But for the last part, I was not really able to understand them. And then I found a comment that details about how to do O(n) solution that codility weirdly did not cover at its best. Here's his comment:
# 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)