如何根据「数据范围」调整自己用什么算法 ...

输入：
A = [1,1,1,0,0,0,1,1,1,1,0], 
K = 2
输出：
6
解释： 
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
复制代码

输入：
A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], 
K = 3
输出：
10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
复制代码

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        // f(i,j) 代表考虑前 i 个数（并以 i 为结尾的），最大翻转次数为 j 时，连续 1 的最大长度
        int[][] f = new int[2][k + 1]; 
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                if (nums[i - 1] == 1) {
                    f[i & 1][j] = f[(i - 1) & 1][j] + 1;
                } else {
                    f[i & 1][j] = j == 0 ? 0 : f[(i - 1) & 1][j - 1] + 1;
                }
                ans = Math.max(ans, f[i & 1][j]);
            }
        }
        return ans;
    }
}
复制代码

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        for (int i = 0; i < n; i++) {
            int l = 0, r = i;
            while (l < r) {
                int mid = l + r >> 1;
                if (check(sum, mid, i, k)) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            if (check(sum, r, i, k)) ans = Math.max(ans, i - r + 1);
        }
        return ans;
    }
    boolean check(int[] sum, int l, int r, int k) {
        int tol = sum[r + 1] - sum[l], len = r - l + 1;
        return len - tol <= k;
    }
}
复制代码

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0, j = 0, tot = 0; i < n; i++) {
            tot += nums[i];
            while ((i - j + 1) - tot > k) tot -= nums[j++];
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}
复制代码