This page discusses different solutions to the problem NumberSolitaire presented by Codility in the lesson 17 “ Dynamic Programming”.
One simple solution is to distinguish between the length of A being less or more than 6.
def solution(A): N = len(A) dp = [A[0]] + [0]*(N-1) for i in xrange(1,min(N,6)): dp[i] = max(dp[:i]) +A[i] for j in xrange(6,N): dp[j] = max(dp[j-6:j]) +A[j] return dp[-1]
The solution above might have the best performance for large inputs of the three solutions on this page. However, the two for-loops could be joined together into one making the solution look neater:
def solution(A): N = len(A) dp = [A[0]] + [0]*(N-1) for j in xrange(1,N): dp[j] = max(dp[max(0,j-6):j]) +A[j] return dp[-1]
Moreover, if we assume that the input array can be modified, then there is no need to create a new list:
def solution(A): for j in xrange(1,len(A)): A[j] += max(A[max(0,j-6):j]) return A[-1]
In any case, all three solutions on this page have the same worst-case time complexity of O(N) and score 100% under Codility’s test.