Short Problem Definition:
In a given array, find the subset of maximal sum in which the distance between consecutive elements is at most 6.
Link
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]