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

Question

我正在尝试解决提供的动态编程部分的 Codility 问题。

A game for one player is played on a board consisting of N consecutive squares, numbered from 0 to N − 1. There is a number written on each square. A non-empty array A of N integers contains the numbers written on the squares. Moreover, some squares can be marked during the game.

At the beginning of the game, there is a pebble on square number 0 and this is the only square on the board which is marked. The goal of the game is to move the pebble to square number N − 1.

During each turn we throw a six-sided die, with numbers from 1 to 6 on its faces, and consider the number K, which shows on the upper face after the die comes to rest. Then we move the pebble standing on square number I to square number I + K, providing that square number I + K exists. If square number I + K does not exist, we throw the die again until we obtain a valid move. Finally, we mark square number I + K.

After the game finishes (when the pebble is standing on square number N − 1), we calculate the result. The result of the game is the sum of the numbers written on all marked squares.

For example, given the following array:

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:

the pebble is on square number 0, which is marked; we throw 3; the pebble moves from square number 0 to square number 3; we mark square number 3; we throw 5; the pebble does not move, since there is no square number 8 on the board; we throw 2; the pebble moves to square number 5; we mark this square and the game ends. The marked squares are 0, 3 and 5, so the result of the game is 1 + 9 + (−2) = 8. This is the maximal possible result that can be achieved on this board.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A of N integers, returns the maximal result that can be achieved on the board represented by array A.

For example, given the array

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.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [2..100,000]; each element of array A is an integer within the range [−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

您可以在 O(N) 中完成与 O(N)额外的空间。

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

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

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

编辑:正如评论中正确指出的@גלעד ברקן，我们可以使用 O(1)空间。为此，我们可以使用长度为 7 的循环缓冲区。