# Codility ‘NumberSolitaire’ Solution

##### Short Problem Definition:

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

NumberSolitaire

##### Complexity:

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

expected worst-case space complexity is O(N)

##### Execution:

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.

##### Solution:
```NR_POSSIBLE_ROLLS = 6
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]
```

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