Java super smart O(n) solution with DP solved follow-up easily


  • 0
    X

    No need to use two pointers. Just visit every element once and maintain 4 variables: res, first, zero and last. res is the maximum result found so far. first is the length of first part of consecutive ones, last is the length of second part of consecutive ones and zero is the length of middle flipped zero. When encounter 1, we update last. When encounter zero, we update first with last, set zero to 1 and set last to 0. Follow-up is solved intrinsically since we don't need to store any part of the input array only the current value.

        public int findMaxConsecutiveOnes(int[] nums) {
            int first = 0, zero = 0, last = 0, res = 0;
            for(int num : nums){
                if(num == 1) last++;
                else{
                    first = last;
                    zero = 1;
                    last = 0;
                }
                res = Math.max(res, first + zero + last);
            }
            return res;
        }
    

Log in to reply
 

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