Dynamic Programming (Codility Q: NumberSolitaire)

Question

This is the question: codility.com/programmers/task/number_solitaire

and below link is my result (50% from Codility): https://codility.com/demo/results/training8AMJZH-RTA/

My code (at the first, I tried to solve this problem using Kadane's Algo):

class Solution {
    public int solution(int[] A) {
        int temp_max = Integer.MIN_VALUE;
        int max = 0;
        int k = 1;

        if(A.length == 2) return A[0] + A[A.length-1];

        for(int i = 1; i < A.length-1; i++) {
            if(temp_max < A[i]) temp_max = A[i];

            if(A[i] > 0) {
                max += A[i];
                temp_max = Integer.MIN_VALUE;
                k = 0;           

            } else if(k % 6 == 0) {
                max += temp_max;
                temp_max = Integer.MIN_VALUE;
                k = 0;
            }
            k++;
        }
        return A[0] + max + A[A.length-1];
    }

And below is the solution (100% from Codility result) that I found from web:

class Solution {
    public int solution(int[] A) {
        int[] store = new int[A.length];
        store[0] = A[0];
        for (int i = 1; i < A.length; i++) {
            store[i] = store[i-1];
            for (int minus = 2; minus <= 6; minus++) {
                if (i >= minus) {
                    store[i] = Math.max(store[i], store[i - minus]);
                } else {
                    break;
                }
            }
            store[i] += A[i];
        }
        return store[A.length - 1];
    }
}

I have no idea what is the problem with my code:(

I tried several test cases but, nothing different with the solution & my code

but, codility test result shows mine is not perfectly correct. (https://codility.com/demo/results/training8AMJZH-RTA/)

please anyone explain me the problem with my code~~

Answer 1

Try this test case[-1, -2, -3, -4, -3, -8, -5, -2, -3, -4, -5, -6, -1]. you solution return -4 (A[0],A[1],A[length-1],Here is the mistake), but the correct answer is -6 (A[0],A[6],A[length-1]).

Here is a my solution,easy to understand:

public int solution(int[] A) {
    int lens = A.length;
    int dp[] = new int[6];
    for (int i = 0; i < 6; i++) {
        dp[i] = A[0];
    }
    for (int i = 1; i < lens; i++) {
        dp[i%6] = getMax6(dp) + A[i];
    }
    return dp[(lens-1)%6];
}

private int getMax6(int dp[]){
    int max = dp[0];
    for (int i = 1; i < dp.length; i++) {
        max = Math.max(max, dp[i]);
    }
    return max;
}

Answer 2

Readable solution from Java:

public class Solution {
    public static void main(String[] args) {
        System.out.println(new Solution().solution(new int[]{1, -2, 0, 9, -1, -2}));
    }

    private int solution(int[] A) {
        int N = A.length;
        int[] dp = new int[N];
        dp[0] = A[0];

        for (int i = 1; i < N; i++) {
            double sm = Double.NEGATIVE_INFINITY;
            for (int j = 1; j <= 6; j++) {
                if (i - j < 0) {
                    break;
                }
                double s1 = dp[i - j] + A[i];
                sm = Double.max(s1, sm);
            }
            dp[i] = (int) sm;
        }

        return dp[N-1];
    }
}

Answer 3

Here is a solution similar to @0xAliHn but using less memory. You only need to remember the last 6 moves.

def NumberSolitaire(A):
    dp = [0] * 6
    dp[-1] = A[0]

    for i in range(1, len(A)):
        maxVal = -100001

        for k in range(1, 7):
            if i-k >= 0:
                maxVal = max(maxVal, dp[-k] + A[i])

        dp.append(maxVal)
        dp.pop(0)
    return dp[-1]