arrays - 数组中的最大总和使得最多可以选择 5 个元素中的 2 个连续

Question

我不知道如何选择元素。

例如，如果我们有 1,2,3,4,5,6,7,8,9,10

我们选择4,5

那我们不能选6,7,8但是我们可以选9

一般来说，我猜

如果我们选择 2 个连续的元素 arr[i] 和 arr[i+1]，

然后我们不能选择接下来的 3 个值 arr[i+2], arr[i+3], arr[i+4] 我们只能选择来自 arr[i+5]

例如:

考虑这个包含9 个元素

的数组

输入:arr[] = {100, 200, 100, 500, 900, 500, 300, 400, 100}

输出:1500

这个的最大金额应该是:1500

通过第4、5、9处取值得到

即 500+900+100 = 1500

另一个例子:

考虑这个包含10 个元素

的数组

输入:arr[] = {500, 700, 300, 500, 900, 700, 600, 400, 700, 500}

输出:2800

选择第(2, 5, 9, 10)处的元素

即 700+900+700+500 = 2800

Answer 1

对我来说，这可以通过对动态规划算法进行简单修改来完成。事实上，您可以添加一个变量来指示是否选择了最后一个元素。假设您正在考虑位置 idx 处的元素，您需要一个变量来告诉您是否选择了 idx - 1:(1) 如果不是，则您还没有选择任何连续的元素，您可以继续idx + 1, (2) 如果是，你应该从idx + 4开始，因为idx+1, idx+2, idx+3已经不允许被pick了。

这是一个 C++ 实现:

    const int n = 1000;

    int arr[n];


    int dp[n][2];
    bool mark[n][2];

    int rec(int idx, bool idx_minus1_picked){
        if(idx >= n){
            return 0; // we have reached end of array
        }

        if(mark[idx][lidx_minus1_picked]){
            return dp[idx][idx_minus1_picked];
        }

        int &ret = dp[idx][idx_minus1_picked];
        ret = 0;

        if(idx_minus1_picked){
            //get the maximum between picking or not picking arr[idx]
            ret = max(arr[idx] + rec(idx + 4, false), rec(idx + 1, false));
        }
        else{
            ret = max(arr[idx] + rec(idx + 1, true), rec(idx + 1, false));
        }

        return ret;

    }

int main(){
    int answer = rec(0, false);
    return 0;
}