There is a simple greedy algorithm.
A greedy approach
The greedy idea is obvious: starting from the very left, extend the coverage to the right as far as possible each time.
However, it may not be obvious to get it right. We should search each next positive interval by the following two criteria:
- It should cover the next uncovered positive entry.
- It should cover as many entries as possible after that entry among all positive intervals that covers that entry.
To boost performance, after the next $u$ncovered positive entry $A[u]$ is found, we will find the optimal start of the positive interval to cover $A[u]$ and the most entries after $A[u]$. That optimal start is an entry such that the sum of entries between it and $A[u]$ is the largest. In fact, that optimal start can be ignored; knowing that largest sum is enough.
Let $\text{sum}(A[i..j])=A[i]+A[i+1]+\cdots+A[j]$, the sum of entries in $A[i..j]$.
Here is the greedy algorithm.
$u\leftarrow0.$ $\ rightmost\leftarrow0.$ $\ answer\leftarrow 0.$ Repeat the following $3$ steps.
- $u\leftarrow$ the least index greater than $rightmost$ at which the entry of $A$ is positive.
If there is no such index, return $answer$.
Otherwise, $answer\leftarrow answer+1$. We will cover $A[u]>0$ and as many entries as possible after it with one positive interval.
- $surplus\leftarrow$ the largest sum among $\text{sum}(A[u..u])$, $\text{sum}(A[u-1..u])$, $\cdots$, $\text{sum}(A[1..u])$.
For the sake of correctness proof, let $start$ be the corresponding starting index of $surplus$, which is the optimal start of the desired positive interval.
- $rightmost\leftarrow$ the largest index $k$ such that $ surplus+\text{sum}(A[u+1..k])>0$, where $u+1\le k\le n$. If there is no such index, $rightmost\leftarrow u$.
Conceptually, we select the positive interval $A[start, rightmost]$.
Complexity Analysis
Each one of step 1, 2 and 3 takes $O(n)$ time.
$u$ starts at $0$ and ends at most $n$. Since $u\le n$ always increases at step 1 unless the algorithm returns, step 1 and hence the whole loop body of step 1, 2, 3 can repeat at most $n$ times. Hence the whole algorithm takes $O(n^2)$ time.
The post here optimizes the approach above to run in $O(n)$ time.
Correctness proof
Let $A[s_1..r_1], A[s_2..r_2], \cdots$ be the positive intervals selected successively by the greedy algorithm. So $r_1<r_2<\cdots$.
Let $A[s_1'..r_1'], A[s_2'..r_2'], \cdots$ be some positive intervals that covers all positive entries in $A$. WLOG, assume $r_1'<r_2'<\cdots$.
Let $s_0=r_0=s_0'=r_0'=0$.
It is enough to prove the greedy algorithm "stays ahead", i.e., $r_i\ge r_i'$ for all $i$.
The case $i=0$ is trivial. Suppose $r_i\ge r_i'$ for some $i$.
Let $u$ and $start=s_{i+1}$ be the values found in the step 1 and 2 of the algorithm that leads to the selected interval $A[s_{i+1}..r_{i+1}]$, i.e., $A[u]$ is the positive entry after $A[r_i]$ and $\text{sum}(A[start..u])$ is the largest among $\text{sum}(A[*..u])$.
Since $r_i'\le r_i<u$, $A[u]$ is not covered by any interval $A[s_j'.. r_j']$, $1\le j\le i$. Hence $A[u]$ is in some $A[s_k'..r_k']$, where $k\ge i+1$.
$$ \text{sum}(A[u+1..r_k'])=\text{sum}(A[s_k'..r_k'])-\text{sum}(A[s_k'..u])>0-\text{sum}(A[start..u])$$
By the step $3$ of the algorithm, the inequality above implies $r_{i+1}\ge r_k'$. Hence $r_{i+1}\ge r_k'\ge r_{i+1}'$.
A Python implementation
While the indices above start with $1$, they start with $0$ in the implementation.
from itertools import accumulate
def minimum_cover(a):
n = len(a)
answer = 0
rightmost = -1
while True:
uncovered = rightmost + 1
while uncovered < n and a[uncovered] <= 0:
uncovered += 1
if uncovered == n:
break
surplus = max(accumulate(a[uncovered::-1]))
new_rightmost = uncovered + 1 + max(
(idx for idx, sm in enumerate(accumulate(a[uncovered + 1:n]))
if surplus + sm > 0), default=-1)
if new_rightmost > rightmost:
rightmost = new_rightmost
answer += 1
return answer
print(minimum_cover([1, 7, -9, 2, -10, -5, 5, -10, 4, -2, 3, -1, 2])) # 2
print(minimum_cover([1, -3, 3, -2, 1, -2, 1])) # 2
