Factor matrix ${\bf A}$ into the product ${\bf B}{\bf C}$ where ${\bf C}$ has no negative entries and ${\bf B}$ has few non-zero entries
Let $v_1, \dots, v_n$ denote the rows of $A$.
Let $u$ be a vector with all positive entries that is not a linear combination of $v_2, \dots, v_n$. Then we may write $v_1 = c u + a_2 v_2 + \dots a_n v_n$ for some scalars $c, a_2, \dots, a_n$.
Now choose $\epsilon$ small enough that for all $j$ from $2$ to $n$, $u + \epsilon \sum_{i=2}^j a_i v_i$ has all positive entries.
Let $C$ be the matrix with rows $u + \epsilon \sum_{i=2}^j a_i v_i$ for $j$ from $1$ to $n$. Then by construction $C$ has all positive entries.
Each vector $v_i$ can be written as a linear combination of two rows of $C$. For $v_i$ this is by subtracting two adjacent rows and dividing by $\epsilon$, and for $v_1$ it is $c-1/\epsilon$ times the first row plus $1/\epsilon$ times the last row.
We conclude that there is a sparse matrix $B$ with $2n$ entries such that $BC = A$.
This is optimal assuming each of the $v_i$ has both positive and negative entries, as the corresponding row of $B$ must have both positive and negative entries and hence at least $2$ entries. If $A$ has any rows that are either non-negative or non-positive, then this algorithm might not be optimal, as the example in the original question shows. However, this algorithm produces matrices where $BC$ is very sensitive to slight changes in $C$ and thus may be unsuitable for practical applications.