Source : Uber offcampus 2021

I am not able to solve 4th problem of coding round and need help to upsolve it.

I put problem statement here also :

Given an array A consisting of N elements, you need to perform the following operations: – remove p elements from the array – remove q groups of consecutive elements of size 2 – remove r groups of consecutive elements of size 3 After performing the operations, the left and right array formed are merged. Output the maximum possible sum after performing the operations.

Constraint: 1 <= N <= 1e5, 1 <= p+2*q+3*r <= N

Example:

Input:

7 1 1 1 //N p q r

4 5 2 1 3 6 7

Output: 7

Explanation:

For p=1, you can remove 1 from the array → [4,5,2,3,6,7]

For q=1, you can remove 2 and 3 which is group of consecutive elements of size 2 → [4,5,6,7]

For r=1, you can remove 4,5 and 6 which is group of consecutive elements of size 3 → [7].The maximum possible sum of array equals to 7.

(Note: There are other ways to remove elements which will give the same result)