Minimal number of positive intervals to cover all positive elements

Question

I'm struggling in finding a correct way to approach this, I'm aware that this problem is solvable using dynamic programming, and this problem somehow relates to the "max non-contiguous subarray" problem, yet I cannot make the connection.

Given an array of integers, $A=(a_1,\ldots , a_n)$ for which $\sum_{i=1}^{n}a_i<0$.

A "Positive Interval" is defined to be a pair of indices $(i,j)$, $1\le i\le j\le n$ such that $\sum_{k=i}^{j}a_k>0$

Describe an algorithm to return the minimal size of group $J$ containing positive intervals in such manner that for all $0<a_\ell\in A$, there is (at least) an interval $(i,j)$ in $J$ such that $i\leq\ell\leq j$.

The intervals can be overlapping, and negative numbers of $A$ dont have to take part in any interval of $J$.

For example, given $A=(1,7,-9,2,-10,-5,5,-10,4,-2,3,-1,2)$ , the algorithm should return $2$, since the "optimal" result would be: $$ J=\{(1,4), (7,13)\} $$ where positive interval $(1,4)$ "covers" elements $1,7,-9,2$ while positive interval $(7,13)$ "covers" elements $5,-10,4,-2,3,-1,2$.

Answer 1

Here is a linear-time solution that consists of the following two parts.

Preparation: compute the prefix sums and the "milestones" among them.

1. Compute the prefix sum array $s$, $s_i=\sum_{k=1}^ia_i$ for all $0\le i\le n$. This is done by setting $s_0=0$ and then $s_{i}=s_{i-1}+a_i$ for $i$ from $1$ to $n$.
2. A prefix sum $s_i, i>0$ is called a milestone if it is bigger than all following prefix sums, i.e., $s_i>s_k$ for all $k>i$.
   Scanning $s_{i}$ for $i$ from $n$ down to $1$, note down the successive strict maximum element found. Reversing the sequence we have noted down, we get all milestones $s_{u_1}, s_{u_2}, s_{u_3}, \cdots$ in the natural order, i.e., $0<u_1<u_2<u_3<\cdots$ and $s_{u_1}>s_{u_2}>s_{u_3}>\cdots$.

It takes $O(n)$ time to run this part.

Greedy: select the "strongly-positive" interval that covers the next uncovered positive element and the most elements after it

A pair of indices $(i,j)$, $i<j$ is viewed as covering all elements in $a$ with indices between $i$ and $j$. It is a strongly-positive interval if it is a positive interval and both $a[i]$ and $a[j]$ are positive. Increasing $i$ and decreasing $j$ if necessary, we can change a positive interval to a strongly-positive interval. If a group of positive intervals cover all positive elements in $a$, we can change each of them whenever necessary so that they becomes a group of strongly-positive intervals that cover all positive elements in $a$ still. Hence it is enough to consider strongly-positive intervals only.

1. Let $\mathit{previous\_target} = -1$, $\mathit{right} = -1$ and $m=-1$.

2. Loop the following.

   1. Try finding the nearest positive element after index $right$. If there is no such element, break the loop. Otherwise, let $\mathit{target}$ be its index.

   2. Among all strongly-positive intervals that cover that positive element, select the one that covers the most elements after that positive element. (If there are several such intervals, select any one of them. We only care about its right end.)

      1. Find the index $\mathit{left}\le\mathit{target}$ such that the sum of elements between $\mathit{left}$ and $\mathit{target}$ is as large as possible.
         That index must be larger than $\mathit{previous\_target}$; otherwise the interval $(\mathit{left},\mathit{target})$ is a strongly-positive interval that covers the element at $\mathit{previous\_target}$ whose right end is larger than $\mathit{right}$, the right end of the interval last selected, which contradict with how that interval was selected.
      2. Increase $m$ by $1$ repeatedly until $u_m\ge\mathit{target}$.
      3. While $s_{u_{m+1}}>s_\mathit{left-1}$, increase $m$ by $1$ .

      The interval we then select is $(\textit{left}, u_m)$. It can be shown this interval is strongly-positive and it covers $a[target]$. Furthermore, it covers the most elements after $a[target]$ among all such intervals. This "greedy property" ensures that the group of strongly-positive intervals we selected "stays ahead" of all other groups of the same number of strongly-positive intervals, i.e., covers no less positive elements since the front of $a$ without missing any positive element in between.

   3. Update $\mathit{previous\_target}$ with $\mathit{target}$. Update $\mathit{right}$ with $u_m$.

3. Return the number of intervals we have selected.

It takes $O(n)$ time to run this part.

An implementation in Python

Please go here at replit.com and click the green "Run" button once or twice to run some basic tests.

Please view the function minimum_positive_intervals(nums) in file main.py that implements the approach above. You may need to click "show files" button and/or "main.py" button first.

Note that while the indices starts with $1$ in the question and this answer, all indices in the implementation starts with $0$.

What if we should also cover nonpositive elements?

The same analysis and algorithm applies, except that we will delete/adjust the requirement/phrases/steps that are related to element positivity.