The following tasks can be performed on an array of integers: 1.Choose a subarray of arr of size 1 at most x times. 2.Choose a subarray of arr of size 2 at most y times. 3.Choose a subarray of arr of size 3 at most z times.
The chosen subarrays should be non-overlapping. The profit is calculated as the sum of the elements maximum profit that can be obtained?
For example,consider the array [1,2,3,4,5] for x,y,and z exqual 1. for x=1 ,choose any one element from the array. The maximum element is 5,so chose that one.it is the maximum profit under this scenario. For y=1,choose andy subarray of two elements:[1,2],[2,3],3,4] or [4,5].The last subarray has the highest sum (profit)of 9. for z=1,the maximum profit is obatained with the subarray [3,4,5] with a sum of 12.
if you can choose one of each, maximum profit would be obtained by ignoring x then using y and z to capture [1,2] and [3,4,5] or [1,2,3] and [4,5] for a total profit of 15.
Constraints: 1<=n<=200 -10^5<=arr[i]<=10^5 0<=x,y,z<=20
Sample Case 0 Sample input 0 n=2 arr[5,3] x=1 y=0 z=0 output 5
Sampe Case 1: n=4 arr[-7,4,0,-7] x=0 y=1 z=0 output 4
What I have tried:
I am not able to find who to solve this question
You know that it is DP, so what states have you tried?
Try to write a backtracking solution and that will give you an idea of the state — the computation is straightforward, as well.
can you solve it
Yes, I can. However, the goal of solving these problems is presumably to improve a skill, so I am giving you a direction/tool instead of the solution directly. If you want to improve, elaborate on what you have tried and why it hasn't worked.
bro seriously this idea that is given by I know but I am unable to implement and write logic If you can provide more info or code so it is good for me
Here is the recursive code-
https://ideone.com/w9iQzW
you can memoise it with dp[idx][x][y][z] to get desired time limit
Think if you have to just solve the problem for the first i element, the choice you have are either not have this element as the ending of any subarray, or have it as the ending of subarray with size 1,2 or 3 so the state should be something like dp[I][x][y][z], this will probably fill in the constraints as well