Max Consecutive Ones II

LintCode Q 883 - Max Consecutive Ones II

Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.

Example 1: Input: nums = [1,0,1,1,0] ; Output: 4
Explanation:
Flip the first zero will get the the maximum number of consecutive 1s.
After flipping, the maximum number of consecutive 1s is 4.

Example 2: Input: nums = [1,0,1,0,1] ; Output: 3
Explanation:
Flip each zero will get the the maximum number of consecutive 1s.
After flipping, the maximum number of consecutive 1s is 3.

Notice:

• The input array will only contain 0 and 1.
• The length of input array is a positive integer and will not exceed 10,000.

Solution

Solution : DP

1. States
   dp[i][0]: the max length until ith number, without flipping numbers
   dp[i][1]: the max length until ith number, with one flipping

Note: dp[i][0] <= dp[i][1]

2. State transfer function
   • if (nums[i] == 1): dp[i][0] = dp[i - 1][0] + 1; dp[i][1] = dp[i - 1][1] + 1;
   • if (nums[i] == 0): dp[i][0] = 0; dp[i][1] = dp[i - 1][0] + 1;

Code:

public int findMaxConsecutiveOnes(int[] nums) {
	
	int[][] dp = new int[nums.length][2];

	// initialize
	if (nums[0] == 1) {
		dp[0][0] = 1; dp[0][1] = 1;
	} else {
		dp[0][0] = 0; dp[0][1] = 1;
	}

	int maxLen = 0;
	for (int i = 1; i < nums.length; i++) {
		if (nums[i] == 1) {
			dp[i][0] = dp[i - 1][0] + 1;
			dp[i][1] = dp[i - 1][1] + 1;
		} else {
			dp[i][0] = 0; 
			dp[i][1] = dp[i - 1][0] + 1;
		}

		maxLen = Math.max(maxLen, dp[i][1]);
	}

	return maxLen;
}

Solution : Improve space complexity

Use two variables flip and not flip to replace the dp[i][0] and dp[i][1].

Code:

public int findMaxConsecutiveOnes(int[] nums) {
	
	int flip = 0;
	int notflip = 0;

	// initialize
	if (nums[0] == 1) {
		flip = 1; notflip = 1; 
	} else {
		flip = 1; notflip = 0;
	}

	int maxLen = 0;
	for (int i = 1; i < nums.length; i++) {
		if (nums[i] == 1) {
			flip++; notflip++;
		} else {
			flip = notflip + 1; notflip = 0;
		}

		maxLen = Math.max(maxLen, flip);
	}

	return maxLen;
}