欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最高连续性

程序员文章站 2024-03-19 22:19:22
...

问题描述:给定数组A,A是元素为0或者1的数组,我们可以更改K个数组中的0,求数组中最大连续子数组的长度。

例子:

最高连续性

算法思路:从0开始依次遍历数组,当某个元素为0的时候将其转换为1,由于我们最终只要求解这个最大连续子数组的长度,因此这里 可以用K-1来表示元素从0转换为1。如果为1,则K不变化。接着要用另外一个变量来记录整体最长子数组的起始位置,即当数组在遍历数组元素到底是0还是1的时候,这个子数组的其实位置也在发生变化,这个子数组整体的在发生变化。

如上面的例子。K=2,当j=3的时候,A[j]=0,这时K--,K=1,当j=4的时候,A[j]=0,K=0,而当j=5,A[j]=10,K--,K=-1,这时相当于把这个位置的0换成了1,表面是违背了题目,但如果将这个最长子数组的起始位置向后移一位,即开始的位置是0,现在将其位置变为1,然后这个最长子数组的长度就是j-i+1,这个就是这个最长子数组的长度了。而当初始的位置为1的时候,表明舍去了一个将0变为1的机会,因此当K<0并且这个起始位置的元素为0的时候,这个K就要加1。这个起始位置只要是当K<0了就要加1。最后j每变化一个就和上一次的最大值进行比较,最终返回这个最大值就OK了。

代码示例:


    public int longestOnes(int[] A, int K) {
        int res=0;
        int i=0;
        for(int j=0;j<A.length;j++)
        {
            if(A[j]==0)
                K--;
            if(K<0&&A[i++]==0)
                K++;
            res=Math.max(res,j-i+1);
        }
        return res;
        
    
    }
}

代码来源思想源自以为大佬,开始还真没想出来,看了半天源码才想出来。。。。。。在博客上面积累。。。。。。。

 

相关标签: