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

Question

I can't work around how to select the elements.

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

and we choose 4,5

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

So, I guess in general

If we choose 2 consecutive elements arr[i] and arr[i+1],

then we CANNOT choose from next 3 values arr[i+2], arr[i+3], arr[i+4] and we may only choose from arr[i+5]

for ex:

Consider this array with 9 elements

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

Output: 1500

Maximum sum for this should be: 1500

Which is obtained by taking the values at places 4, 5 and 9

i.e 500+900+100 = 1500

Another example:

Consider this array with 10 elements

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

Output: 2800

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

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

or 500 + 900 + 400? I'm not quite understanding the question. — Gavin Achtemeier
We can't take (500+900+500) in the first example as there will be 3 consecutive selections, We are allowed to have ATMOST 2 consecutive selections. — Guest99318
is it two consecutive per group of five or two in any group of five? — Gavin Achtemeier
how about if i pick non consecutive numbers? eg: i pick all number at index 0,2,4,6,8... is that valid? — shole

A. Mashreghi A. Mashreghi · Accepted Answer · 2017-07-28T04:44:15

To me this can be done using a simple modification to the dynamic programming algorithm. In fact, you can add a variable to indicate if the last element was picked or not. Let's say that you are considering the element at position idx, you need a variable to tell you if idx - 1 is picked or not: (1) If it isn't, you haven't picked any consecutive yet and you can continue at idx + 1, (2) If it is, you should start from idx + 4, since idx+1, idx+2, idx+3 are not allowed to be picked anymore.

Here is an 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; // 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;
}

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

1 Answers