I have just started Dp. I am stuck in a problem of codeforces. I’m not able to find the approach. Please share your approaches.
Any suggestions for a beginner??
I think this is an application of kadane’s algorithm.
how?
Find the number of initial ones. Replace all 1s with -1 and all 0s with 1. Then add the largest non empty subarray in our new array.
why?
Each ‘1’ we flip, we’ll lose a ‘1’ which decreases the count.
Each ‘0’ we flip, we’ll get a ‘1’ increasing the count.
Now we just have to find the subarray increasing count the most.
Don’t worry too much. Practice a bit, for example atcoder dp contest, and most dp questions will look obvious
1 Like