# O(n) time and O(k) space Very Easy Solution for Any K Flips and Stream Input

• It is similar to the Stock Buy and Sell K Times problem. We can use dynamic programming to solve this problem.

Supposed that we can flip k zeros, and we use cnt[k] to represents the maximum length if we flip exactly k zeros.
So cnt[0] is the maximum length if we do not flip any zero.

If we encounter a '1', then every cnt[i] (0 <= i <= k) should increase one.

If we encounter a '0', since cnt[k] means we already flip k times, so we can not flip any more zero, this the current maximum length, we update the result by "res = max(res, cnt[k])". For cnt[k-1], we still can flip one zero, do it, then we can update cnt[k] by "cnt[k] = cnt[k-1] + 1". In this way, we can update all cnts except cnt[0]. In fact, cnt[0] shuld be 0.

After processing all numbers from the stream, we need look at all cnts and update result if there is a bigger number.

``````    int findMaxConsecutiveOnes(vector<int>& nums) {
int k = 1; // flip at most k zeros
vector<int> cnt(k + 1, 0);
int res = 0;

for (int i: nums) {
if (i == 1) {
for (int &c: cnt) {
++c;
}
} else {
res = max(res, cnt[k]);
for (int j = k; j > 0; --j) {
cnt[j] = 1 + cnt[j - 1];
}
cnt[0] = 0;
}
}

for (int i: cnt) {
res = max(res, i);
}

return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.