LC: Max Consecutive Ones II - spiralgo/algorithms GitHub Wiki
The Essence:
Points:
- Putting a 0 means connecting 2 blocks of 1's.
- When the pointer is inside a block of 1's, that means that it is either on the left or the united-right side of the block.
- Hitting a zero should set the length of the previous 1's block as the left. After that, the right part should also be counted for next hitting of 0 after that block of 1's.
Details:
- When the index hits a 0, that means that the index will move on to the right block. The united block assumes the length left+1, the procedure should increment it with coming 1's if present after the 0. The left's length becomes 0 (It becomes the left of a new possible block).
- Each time, the program can check if the length of the united block is better than our previous best, or it can do this upon hitting a 0.
The code implementation can be found here: https://github.com/spiralgo/algorithms/blob/master/src/main/java/algorithms/curated170/medium/MaxConsecutiveOnes2.java