arrays - 统计至多 k 个奇数的子数组

Question

最近遇到一个问题如下。

给定一个数组，计算最多有 m 个奇数的不同子数组的数量。

我知道如何解 m 个奇数。想知道这是否也可以在 O(n) 中解决？有什么想法吗？

Answer 1

恰好 m 个奇数的解很可能会找到，对于每个起始点 i，最右边的端点 r(i)子数组。

剩下的就是说，对于最多 m 个奇数，每个起点 i 都有 r(i) - i + 1 端点的可能性。