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

Question

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

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

，我们选择4,5

那么我们就不能选择6,7， 8，但我们可以选择9号

所以，我想一般

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

那么我们CAN NOT从下一个3个值选择ARR第[i + 2]，ARR第[i + 3]，ARR第[i + 4]并且我们可以仅从ARR第[i + 5]

为前选择：

考虑这个数组9元件

输入：常用3 [] = {100，200，100，500，900，500，300，400，100}

输出：1500

该最大总和应该是：1500

这是由在位置4,5和9

取值获得，即500 + 900 + 100 = 1500

又如：

考虑这个数组10个元素

输入：常用3 [] = {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不允许再被选取。

这是在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; 
}