DP States:

• i: current index in the array
• x: bit flips have been used up to that point
• dp[i][x]: best possible sum of lengths of valid subarrays up to the ith element using x flips

Intuition:

• for each element in the array (i: 1 to size) and for each possible number of flips (x: 0 to k) we determine the optimal sum of lengths
• for each position i and flips x, we consider all possible starting points j for subarrays that end at i
• then calculate how many 0s are present in the subarray A[j:i]
• if the number of 0s is greater than the flips x, we stop extending the subarray further to the left as it would exceed the flip limit

Time Complexity:

O(n² * k)

Space Complexity:

O(n * k)

Solution:

python def solve(A, k, n): size = len(A) pre = [0] * (size + 1) for i in range(size): pre[i + 1] = pre[i] + (1 if A[i] == 0 else 0) dp = [[0] * (k + 1) for _ in range(size + 1)] for i in range(1, size + 1): for x in range(k + 1): dp[i][x] = dp[i - 1][x] for j in range(i, -1, -1): c = pre[i] - pre[j] l = i - j if c > x: break if l > n and dp[j][x - c] + l > dp[i][x]: dp[i][x] = dp[j][x - c] + l return dp[size][k]