Java solution, easy to understand


  • 0
    A
    class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        // algorithm 2017/09/02: DP-like solution
        // - we use localMax_intact  to record the localMax if no number is changed
        //          localMax_flipped to record the localMax if the current number 0 is flipped to 1
        if (null == nums || 0 == nums.length) {
            return 0;
        }
        
        int globalMax_flipped = 0;
        int localMax_intact   = 0;
        int localMax_flipped  = 0;
        
        for (int index = 0; index < nums.length; index++) {
            int num = nums[index];
            
            if (1 == num) {
                localMax_intact  ++;
                localMax_flipped ++;
            } else {
                // we meet 0 -- what if we flip this particular one to 1?
                if (0 == index || 0 == nums[index-1]) {
                    localMax_flipped = 1;   // first 0, or previous one is 0, then localMax_flipped is 1
                } else {
                    localMax_flipped = localMax_intact + 1; // previous one is 1, then we use localMax_intact to increase by 1
                }
                localMax_intact = 0;    // reset localMax_intact, but not localMax_flipped
            }
            
            // recalc globalMax for each move
            globalMax_flipped = Math.max(globalMax_flipped, localMax_flipped);
        }
        
        return globalMax_flipped;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.