The following question is convertible to Kadane’s: Maximize number of 0s by flipping a subarray

In Approach 2, I’m not clear why the solution considers every 0 as -1 and every 1 as 1.

The following question is convertible to Kadane’s: Maximize number of 0s by flipping a subarray

In Approach 2, I’m not clear why the solution considers every 0 as -1 and every 1 as 1.

So basically flipping and an with maximum 1’s minimum 0’s is what we want. Thats why if we take 1 as 1 and 0 and -1 and find max_subarray_sum, our task would be done, because this will increment the count by 1 for every ‘1’ in the array and decrement by -1 for every ‘0’ in array. So it stores maximum difference we can actually achieve by flipping task. Flipping task + number of 0’s in the array is the required answer.

1 Like