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

Question

我无法解决如何选择元素的问题。

所以，我想总的来说

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

然后我们不能从接下来的3个值Arr[i+2]、Arr[i+3]、Arr[i+4]中选择，我们只能从Arr[i+5]中选择

取第4、5和9位的值

即500+900+100=1500

另一个例子：

即700+900+700+500=2800

Answer 1

对我来说，这可以通过对动态规划算法的简单修改来实现。实际上，您可以添加一个变量来指示最后一个元素是否被选中。假设您正在考虑位于idx位置的元素，您需要一个变量来告诉您是否选择了idx-1：（1）如果不是，您还没有选择任何连续的，您可以在idx+1继续，(2)如果是，您应该从idx+4开始，因为不再允许选择idx+1、idx+2、idx+3。

下面是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;
}