Solution to Number-Solitaire by codility

5 Replies to “Solution to Number-Solitaire by codility”

1. A more memory efficient solution can be achieved by only storing the last 6 values.

   1 2 3 4 5 6 7

   def solution(A):     d = 6     n = len(A)     max_score = [A[0]] * d     for p in xrange(1, n):         max_score[p % d] = max(max_score) + A[p]     return max_score[(n - 1) % d]

   Reply

   • Great implementation! Thanks for sharing!

     Reply

2. I knew I can find a better solution here! 🙂 I didn’t realize that the space complexity can be reduced to O(1)! Hooray, Charles!
   Here is my boring text-book-like solution

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   #include <vector> #include <limits> #include <algorithm> using namespace std; int solutionNumberSolitaire(const vector<int> &A) {     int len = A.size();     vector<long> memo(len, numeric_limits<long>::min());     memo[0] = A[0];     for (int i = 1; i < len; ++i)     {         for (int j = 1; j <7; ++j)         {             if (i - j >= 0)                 memo[i] = std::max(memo[i], A[i] + memo[i - j]);         }     }     return memo[len - 1]; }

   Reply

3. 1 2 3 4 5 6 7 8 9 10 11 12 13 14

   #include <algorithm> int solution(vector<int> &A) {        vector<int> temp(A.size(), -1);     temp[0] =  A[0];     for(unsigned int i = 1;i< A.size();i++)     {         int j =  i<6? 0: (i- 6);        auto itr = std::max_element(temp.begin() + j, temp.begin() + i);        temp[i] = (*itr +  A[i]);              }     return temp[A.size() - 1]; }

   Reply

4. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   def solution(A):     K = 6     N = len(A)     dp = [0] * N     for i in range(N-1,-1,-1):         max_val = -10000000000                  if i == N-1:             dp[i] = A[i]         else:             for k in range(K,0,-1):                 if k + i <= N -1:                     dp[i] = max(max_val, A[i]+dp[i+k])                     max_val = dp[i]     return dp[0]

   Reply