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.
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 # 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.