Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.  

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation: 
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation: 
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined. 

Note:

1. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] is 0 or 1 

---

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。 

示例 1：

输入：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。

示例 2：

输入：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。 

提示：

1. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] 为 0 或 1 

---

Runtime: 576 ms Memory Usage: 18.9 MB

 1 class Solution {
 2     func longestOnes(_ A: [Int], _ K: Int) -> Int {
 3         var n:Int = A.count
 4         var pre:[Int] = [Int](repeating:0,count:n)
 5         for i in 0..<n
 6         {
 7             if A[i] == 0
 8             {
 9                 pre[i] = 1
10             }
11         }
12         for i in 1..<n
13         {
14             pre[i] = pre[i - 1] + pre[i]
15         }
16         var fans:Int = 0
17         for i in -1..<(n - 1)
18         {
19             var lo:Int = i + 1
20             var hi:Int = n - 1
21             var ans:Int = i
22             while(lo <= hi)
23             {
24                 var mid:Int = (lo + hi) / 2
25                 var val:Int = pre[mid]
26                 if i >= 0
27                 {
28                     val -= pre[i]
29                 }
30                 if val <= K
31                 {
32                     ans = mid
33                     lo = mid + 1
34                 }
35                 else
36                 {
37                     hi = mid - 1
38                 }                
39             }
40             fans = max(fans, ans - i)
41         }
42         return fans    
43     }
44 }