从给定数组中找出最大和的子集，其中连续元素之间的距离最多为6

Question

我正试图解决所提供的动态编程部分的一致性问题。

一个玩家的游戏在由N个连续方块组成的棋盘上进行，编号从0到N − 1。每个方块上都写着一个数字。由 N 个整数组成的非空数组 A 包含写在正方形上的数字。此外，一些方块可以在游戏过程中标记。

游戏开始时，在方块0上有一块鹅卵石，这是棋盘上唯一被标记的方块。游戏的目标是将鹅卵石移动到方块数字N−1。

在每个回合中，我们投掷一个六面骰子，其表面上有从1到6的数字，并考虑数字K，该数字在骰子静止后显示在上脸上。然后，我们将站在平方数 I 上的鹅卵石移动到平方数 I K，前提是该平方数 I K 存在。如果平方数I K不存在，我们再次掷骰子，直到我们获得有效的移动。最后，我们标记平方数I K。

游戏结束后（当卵石站在N号方格上时− 1） ，我们计算结果。游戏的结果是写在所有标记方块上的数字之和。

例如，给定以下数组：

A[0] = 1
A[1] = -2
A[2] = 0
A[3] = 9
A[4] = -1
A[5] = -2 one possible game could be as follows:

鹅卵石位于正方形数字0上，该正方形数字被标记;我们扔3;鹅卵石从正方形数0移动到正方形数3;我们标记正方形数字3;我们扔5;鹅卵石不会移动，因为棋盘上没有正方形数字8;我们扔2;鹅卵石移动到数字5的正方形;我们标记这个广场，游戏结束。标记的正方形是 0、3 和 5，因此游戏的结果为 1 9 （−2） = 8。这是在该板上可以实现的最大可能结果。

编写函数：

class Solution { public int Solution(int[]A)；}

给定一个N个整数的非空数组A，返回由数组A表示的棋盘上可以达到的最大结果。

例如，给定数组

A[0] = 1
A[1] = -2
A[2] = 0
A[3] = 9
A[4] = -1
A[5] = -2 the function should return 8, as explained above.

为以下假设编写一个有效的算法：

n是范围[2]内的整数..100,000];数组A的每个元素都是一个范围在-10，000内的整数..10,000].

我在网上裁判那里表现很差。

我的解决方案如下。

public static int solution(int[] A) {

        int N = A.length;

        int[] result = new int[N];
        result[0] = A[0];

        for (int i = 1; i < N; i++) {

            result[i] = result[i - 1];

            for (int j = 2; j <= 6; j++) {

                if (j > i) {
                    break;
                }

                // 0, 1, 2, 3, 4
                result[i] = Math.max(result[i], result[j - 2]);
            }

            result[i] += A[i];
        }

        return result[N - 1];
    }

我如何提高正确性和性能？

Answer 1

def solution_dp(A):
    # Initialize dp all with zeros. This essentially stores sum 
    # we can obtain till that index

    dp = [0] * len(A)
    

    # Sum we obtain at 0th index is the first element itself  
 
    dp[0] = A[0]

    # For the rest of the sum, it is the maximum of the last 6 elements 
    # plus the current number. Notice that last 6 element will not exist for 
    # i < 6, so we do max(0,i-6)

    for i in range(1, len(A)):
        dp[i] = max(dp[max(0, i-6):i]) + A[i]
    
    # Since we want sum we get arriving at last index we return last sum
    return dp[-1]

时间复杂度：O（N）

空间复杂度：O（N）

Answer 2

有趣的是，当我替换掉行< code > result[I]= math . max(result[I]，result[j-2])；用行< code > result[I]= math . max(result[I]，result[I-j])；我完全正确。

公共静态int解决方案（int[]A）{

    int N = A.length;

    int[] result = new int[N];
    result[0] = A[0];

    for (int i = 1; i < N; i++) {

        result[i] = result[i - 1];

        for (int j = 2; j <= 6; j++) {

            if (j > i) {
                break;
            }

            // 0, 1, 2, 3, 4
            result[i] = Math.max(result[i], result[i-j]);
        }

        result[i] += A[i];
    }

    return result[N - 1];
}

Answer 3

您可以在具有< code>O(N)额外空间的< code>O(N)中执行此操作。

分配长度为< code>N的数组< code>dp,对于数组中的每个下一项，通过以下公式找出游戏的最大可能值:

dp[k] = max(dp[k-6], dp[k-5], .., dp[k - 1]) + data[k]

数组开头需要一些特殊处理。答案将存储在dp[N-1]中。

编辑：正如评论中正确指出的那样 @גלעד ברקן，我们可以用 O（1） 空格来做到这一点。为此，我们可以使用长度为 7 的圆形缓冲区。