Short Problem Definition:
Find the maximal sum of any double slice.
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N)
To solve this task, you need to keep track of two slice arrays. The optimal double slice can be found at an index that has the maximal sum of those two arrays. It can not be the 0th or the last index.
def solution(A): ending_here =  * len(A) starting_here =  * len(A) for idx in xrange(1, len(A)): ending_here[idx] = max(0, ending_here[idx-1] + A[idx]) for idx in reversed(xrange(len(A)-1)): starting_here[idx] = max(0, starting_here[idx+1] + A[idx]) max_double_slice = 0 for idx in xrange(1, len(A)-1): max_double_slice = max(max_double_slice, starting_here[idx+1] + ending_here[idx-1]) return max_double_slice
If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.