Question: https://codility.com/demo/take-sample-test/number_solitaire/

Question Name: Number-Solitaire or NumberSolitaire

The key point is: to achieve the position i, we can only come from the positions i-6, i-5, i-4, i-3, i-2, and i-1.

1 2 3 4 5 6 7 8 9 10 11 | def solution(A): # The first six items are used for padding only, so that we can have # a unified for loop, no matter how many squares are there in input. # The first item is never accessed. max_so_far = [A[0]] * (len(A) + 6) for index in xrange(1, len(A)): # Because we have a fixed length of window as 6, the time # complexity of max(max_so_far[index : index + 6]) is O(1). max_so_far[index + 6] = max(max_so_far[index : index + 6]) + A[index] return max_so_far[-1] |

A more memory efficient solution can be achieved by only storing the last 6 values.

Great implementation! Thanks for sharing!

I knew I can find a better solution here! ðŸ™‚ I didn’t realize that the space complexity can be reduced to O(1)! Hooray, Charles!

Here is my boring text-book-like solution