MaxDoubleSliceSum 100% Solution in python
Question
My Solution
def solution(A): fromStartMaxEnding = [0] * len(A) for i in range(1, len(A)-1): fromStartMaxEnding[i] = max(0, fromStartMaxEnding[i-1]+A[i]) fromEndMaxEnding = [0] * len(A) for i in range(len(A)-2, 0, -1): fromEndMaxEnding[i] = max(0, fromEndMaxEnding[i+1]+A[i]) ans = -1 * 2**23 for i in range(1, len(A)-1): ans = max(ans, fromStartMaxEnding[i-1] + fromEndMaxEnding[i+1]) return ans
Note
rafal.io It seems that this algorithm doesn't handle with the situation in which all the elements in A is negative? I think the trick is that the selection triplet can be (1, 2, 3), which actually selects nothing from the definition yielding the answer to be zero as calculated by this algorithm.