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+2q+3r <= 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)