Codility 'NumberSolitaire' Solution

Martin Kysel · December 23, 2014

Short Problem Definition:

In a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6.



expected worst-case time complexity is O(N)

expected worst-case space complexity is O(N)


Prototypical Dynamic Programming. Remember all sub-solutions and use them to compute the next step. I prefixed the array by 6 min_values to use the same computation for the whole algorithm (besides the first). Do not forget to set the minimal_value small enough to handle a purely negative input array.


MIN_VALUE = -10000000001

def solution(A):
    sub_solutions = [MIN_VALUE] * (len(A)+NR_POSSIBLE_ROLLS)
    sub_solutions[NR_POSSIBLE_ROLLS] = A[0]
    # iterate over all steps
    for idx in xrange(NR_POSSIBLE_ROLLS+1, len(A)+NR_POSSIBLE_ROLLS):
        max_previous = MIN_VALUE
        for previous_idx in xrange(NR_POSSIBLE_ROLLS):
            max_previous = max(max_previous, sub_solutions[idx-previous_idx-1])
        # the value for each iteration is the value at the A array plus the best value from which this index can be reached
        sub_solutions[idx] = A[idx-NR_POSSIBLE_ROLLS] + max_previous
    return sub_solutions[len(A)+NR_POSSIBLE_ROLLS-1]

Twitter, Facebook