Given an array arr[] consisting of 0’s and 1’s. A flip operation is one in which you turn 1 into 0 and a 0 into 1.You have to do atmost one “Flip” operation on a subarray. Then finally display maximum number of 1 you can have in the array.
I did not know this was a DP problem before I checked the tag. I am kind of confused how to proceed with the problem right now. Any ideas/hints are massively appreciated. So far I thought of some things which arent quite correct such as
- DP[i] = Max # of 1's in subarray [0,...,i]
- DP[i] = Max # of 1's in subarray [0,...,i] if you flip at index i
I am thinking second one might be an idea, but I can't find a optimal structure for "recursion."
Thanks