动态编程（Codility Q：NumberSolitaire） -博客-wpsshop博客

这是一个问题：codility.com/programmers/task/number_solitaire

和下面的链接是我的结果（来自Codility的50％）：https ://codility.com/demo/results/training8AMJZH-RTA/

我的代码（最初，我尝试使用Kadane的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];
    }

下面是我从网络上找到的解决方案（Codility结果的100％）：

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];
    }
}

我不知道我的代码是什么问题:(

我尝试了几个测试用例，但是解决方案和我的代码没有什么不同

但是，Codility测试结果表明我的并不完全正确。（https://codility.com/demo/results/training8AMJZH-RTA/）

请有人用我的代码向我解释问题~~

试试这个测试案例[-1，-2，-3，-4，-3，-8，-5，-2，-3，-4，-5，-6，-1]。您的解决方案返回-4（A [0]，A [1]，A [长度-1]，这是错误），但正确答案是-6（A [0]，A [6]，A [长度-1]）。

这是我的解决方案，很容易理解：

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;
}