Codility 'MaxSliceSum' Solution

Martin Kysel · December 29, 2014

Short Problem Definition:

Find a maximum sum of a compact subsequence of array elements.



expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)


Can be solved by slightly adapting the golden_max_slice from the tutorial, not allowing empty slices.


def golden_max_slice(A):
    max_ending = max_slice = -1000000
    for a in A:
        max_ending = max(a, max_ending +a)
        max_slice = max(max_slice, max_ending)
    return max_slice

def solution(A):
    return golden_max_slice(A)

Twitter, Facebook

To learn more about solving Coding Challenges in Python, I recommend these courses: Python Algorithms, Python Coding Interview.