I’m not able to think of a way to solve this question using dp. In hint video they have given the optimal solution but i want to learn using dp on it. Please tell the method
Not able to solve
post the question also, so that I can help you
Closing this for now. Open it again if you want.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
Given an array of size n with 0s and 1s , flip at most k 0s to get the longest possible subarray of 1s. Input Format First Line : n, size of array and k Second Line : n space separated numbers (0s or 1s) Constraints n <= 10^5 0 <= k <= n Output Format First Line : Size of subarray Second Line : Array after flipping k 0s Sample Input 10 2 1 0 0 1 0 1 0 1 0 1 Sample Output 5 1 0 0 1 1 1 1 1 0 1
i want to solve it using dp
maintain a 2d DP to memoise this
at each point when u encounter a zero u have two options either to flip it or not
if yes, you flip it, increase the amount of flips and check that upto this point what is the largest sequence of ones, for that u r going to keep another variable for it
if u decide to not flip it, u can make the flips as zero and consecutive ones as zero
if 1 is encountered increase the consecutives and do not change the flips
and what should be the dimensions of the 2d dp? I’m not quite clear yet as to when use 2d dp and when 1d dp. Can you please help in that also
sir please reply .
When to use 1d and 2d, see it depends on the number of parameters u need to mind, like here u need both length and last bit
so what will be the dimensions of the 2d dp in this case?
as in the name “2D” so 2 dimensions, could also be solved using 3D