##### Short Problem Definition:

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

##### Link

##### Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(N)

##### Execution:

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

##### Solution:

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)

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.