algorithm - Maximum sum in array such that atmost 2 consecutive in 5 elements can be selected -

i can't work around how select elements.

for example if have 1,2,3,4,5,6,7,8,9,10

and choose 4,5

then cant choose 6,7,8 can choose 9th

so, guess in general

if choose 2 consecutive elements arr[i] , arr[i+1],

then cannot choose next 3 values arr[i+2], arr[i+3], arr[i+4] , may choose arr[i+5]

for ex:

consider array 9 elements

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

output: 1500

maximum sum should be: 1500

which obtained taking values @ places 4, 5 , 9

i.e 500+900+100 = 1500

another example:

consider array 10 elements

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

output: 2800

select elements @ (2, 5, 9, 10)

i.e 700+900+700+500 = 2800

to me can done using simple modification dynamic programming algorithm. in fact, can add variable indicate if last element picked or not. let's considering element @ position idx, need variable tell if idx - 1 picked or not: (1) if isn't, haven't picked consecutive yet , can continue @ idx + 1, (2) if is, should start idx + 4, since idx+1, idx+2, idx+3 not allowed picked anymore.

here implementation in 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; // 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 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; }