给定一个二进制数组 nums ，如果最多可以翻转一个 0 ，则返回数组中连续 1 的最大个数。
示例 1：
输入：nums = [1,0,1,1,0] 输出：4 解释：翻转第一个 0 可以得到最长的连续 1。 当翻转以后，最大连续 1 的个数为 4。
示例 2:
输入：nums = [1,0,1,1,0,1] 输出：4
提示:
1 <= nums.length <= 105nums[i]不是0就是1.
进阶：如果输入的数字是作为 无限流 逐个输入如何处理？换句话说，内存不能存储下所有从流中输入的数字。您可以有效地解决吗？
Related Topics
【动态桂花】详细分析总结过程
自己写个例子试一下看看[1,0,1,1,0,0,1,1,1,1,0]
定义两个值，一个定义当遍历中的这段有连续多长了。
另一个表示如果翻转这个位置的0变成1能得到连续多长的1字符，如果不是0则之前的连续长度加1
如下
1,0,1,1,0,0,1,1,1,1,0
a) 1 0 1 2 0 0 1 2 3 4 0
b) 1 2 3 4 3 1 2 3 4 5 5
分析下
- 第一位为
1，则a表示的，当前可以得到的连续长度为1，b同样，如果第一位为0的话，a等于0，b依旧等于1 - 第二位为
0，a的连续性中断了，此时a等于0，b的话可以在之前的a等于1的后面转换一个得到长度为2 - 第三位为
1，此时a继续等于1，b可以在之前的长度上继续延长得到3 - 第四位为
1，同上一步a等于2，b等于4 - 第五位为
0，a的连续性中断了，此时a等于0。如果翻转这里的0可以得到和前面的a等于相连，得到长度为3的连续1数字 - 第六位依旧为
0，a依旧等于0，b只能和前面的第五位的时候的a等于0相连得到长度为1的连续数字1 - 第七位变为了
1，a这里等于1了，b可以连着前面的，此时b等于2 - 第八、九、十位，都是
1，按照前面的规律依次叠加，最终a等于4，b等于5 - 最后第十一位
0，这里的a再次变为0，而把这里的0翻转为1的话只能和前面的第十位的a等于4相连得到一个连续5位的数组1 - 在这个过程中保存b得到的最大值
确实，动态规划这个问题的代码本身并不是非常难写，困难的是如何总结归纳出正确的转移方程，如何定义出正确的dp数组赋予正确的定义
//当前位置为0 dp[i][0] = 0 dp[i][1] = dp[i-1][0]+1 //当前位置为1 dp[i][0] = dp[i-1][0]+1 dp[i][1] = dp[i-1][1]+1
代码
class Solution {
public int findMaxConsecutiveOnes(int[] nums) {
int[][] dp = new int[nums.length][2];
dp[0][0] = nums[0];
dp[0][1] = 1;
int idx = 0;
int max = 1;
while (++idx < nums.length){
dp[idx][0] = nums[idx] == 0?0:dp[idx-1][0]+1;
dp[idx][1] = nums[idx] == 0?dp[idx-1][0]+1:dp[idx-1][1]+1;
max = Math.max(max,dp[idx][1]);
// System.out.println(Arrays.toString(dp[idx]));
}
return max;
}
}继续优化的版本就省略了，其实看下上面的分析步骤就可以自己非常容易的总结出如何进一步优化了
发表评论