We have a bit array like below

```
{1 0 1 0 0 1 0 1}
```

Number of bits in above array is 8

If we take range from `[1,5]`

then number of bits in `[1,5]`

range is `[0 1 0 0 1]`

.

If we flip this range then after flipping it will be `[ 1 0 1 1 0]`

So total number of 1’s after flipping `[1,5]`

range is `[1 1 0 1 1 0 0 1] = 5`

If we take range from `[1,6]`

then number of bits in [1,6] range is `[0 1 0 0 1 0]`

.

If we flip this range then after flipping it will be `[ 1 0 1 1 0 1]`

So total number of 1’s after flipping [1,5] range is `[1 1 0 1 1 0 1 1] = 6`

So the answer is range `[1,6]`

and after flipping we can get 6 1’s in array

**Solution** : use dynamic programming to solve it. dp[i, j] indicates from i to j, if we flip, how many more 1s we can get comparing to nonflip array.

public int flipBits(int[] a) { var res = 0; var dp = new int[a.Length, a.Length]; for (int i = 0; i < a.Length; i++) { if (a[i] == 0) { dp[i, i] = 1; } else { dp[i, i] = -1; } res = Math.Max(res, dp[i, i]); } for (int i = 0; i < a.Length; i++) { for (int j = i + 1; j < a.Length; j++) { if (a[j] == 0) { dp[i, j] = dp[i, j - 1] + 1; } else { dp[i, j] = dp[i, j - 1] - 1; } res = Math.Max(res, dp[i, j]); } } return res + a.Count(x => x == 1); }

**Solution 2**: Change to subarray problem, use Kadane’s algorithm to get it. by changing all 0s to -1s, then the problem is to find smallest contiguous subarray.

See here for more information.

public int flipBits2(int[] a) { // change all 0s to -1s for (int i = 0; i < a.Length; i++) { if (a[i] == 0) { a[i] = -1; } } var smallestGlobal = 0; var smallestSoFar = 0; foreach (int x in a) { smallestSoFar += x; if (smallestSoFar > 0) smallestSoFar = 0; smallestGlobal = Math.Min(smallestGlobal, smallestSoFar); } return (-1) * smallestGlobal + a.Count(x => x == 1); }