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.
Solution to Number-Solitaire by codility
# 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] * (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 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