动态编程（Codility Q：NumberSolitaire）

Question

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

以下链接是我的结果（50％来自Codility）：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];
    }

以下是我在网上找到的解决方案（100％来自Codility结果）：

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

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

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

但是，能力测试结果显示我的不完全正确。 （https://codility.com/demo/results/training8AMJZH-RTA/）

请任何人用我的代码解释我的问题~~

Answer 1

试试这个测试用例[-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;
}

Answer 2

因为您没有使用动态编程，所以您使用的是贪婪的算法。当范围中的最大数字不是正确的选择时，您的代码将失败。

function solution(A) {
  // This array contains maximal value at any index.
  const maxTill = [A[0]];

  // It's a dynamic programming so we will choose maximal value at each
  // Index untill we reach last index (goal)
  for (let i = 1; i < A.length; i++) {
    // Step 1 . max value of each index will be atleast equal to or greater than
    // max value of last index.
    maxTill[i] = maxTill[i - 1];
    // For each index we are finxing the max of last 6 array value
    // And storing it into Max value.
    for (let dice = 1; dice <= 6; dice++) {
      // If array index is itself less than backtrack index
      // break as you dont have 6 boxes in your left
      if (dice > i) {
        break;
      } else {
        // The most important line .
        // Basically checking the max of last 6 box using a loop.
        maxTill[i] = Math.max(
          maxTill[i - dice],
          maxTill[i]
        );
      }
    }
    // Untill this point maxStill contains the maximal value
    // to reach to that index.
    // To end the game we need to touch that index as well , so
    // add the vale of the index as well.
    maxTill[i] += A[i];
  }
  return maxTill[A.length - 1];
}

console.log(solution([-1, -2, -3, -4, -3, -8, -5, -2, -3, -4, -5, -6, -1]));

Answer 3

这是我的解决方案。我尝试使代码易于理解。它可能无法尽可能多地节省空间。

    private static int solution(int A[])
{   
    // N //  N is an integer within the range [2..100,000];
    // A[] // each element of array A is an integer within the range [−10,000..10,000].
    int N = A.length;
    int[] bestResult = new int[N]; // record the current bestResult
    Arrays.fill(bestResult, Integer.MIN_VALUE); // fill in with the smallest integer value

    // initialize
    bestResult[0] = A[0];
    for (int i = 0;i < A.length;i++) {
        // calculate six possible results every round
        for (int j = i + 1; (j < A.length) && (i < A.length) && j < (i + 1) + 6; j++) {
            // compare
            int preMaxResult = bestResult[j]; // the max number so far
            int nowMaxResult = bestResult[i] + A[j]; // the max number at bestResult[i] + A[j]
            bestResult[j] = Math.max(preMaxResult, nowMaxResult);
        }
    }        
    return bestResult[bestResult.length-1];
}

Answer 4

这是简单的Python 3解决方案：

import sys

def solution(A):        
    dp = [0] * len(A)
    dp[0] = A[0]

    for i in range(1, len(A)):
        maxVal = -sys.maxsize - 1

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

        dp[i] = maxVal
    return dp[len(A)-1]