Maximizing length of subsequence

Question

Given a sequence $(a)$ of lenght $n$, such $a_1 = a_n = 1$ and $a_i \in \left \{ -1, 1 \right\}$.

We want to find a subsequence $(b) \subset (a)$ which statisfies the following conditions:

• The length of $(b)$, (let's call it $k$) is the largest possible
• $b_k = b_1 = 1$
• Each prefix sum $b_1$, $b_1+b_2$, $b_1+b_2 + b_3,\ \ldots\ , b_1 + b_2 + \ldots + b_k$ is $\geq 0$.
• Each suffix sum $b_k$, $b_{k} + b_{k-1}, b_{k} + b_{k-1} + b_{k-2}, \ \ldots\ , b_k + b_{k-1} + \ldots + b_1$ is $\geq 0$.
• Sum of $(b)$ is the biggest possible.

Is it possible to construct linear algorithm to solve it?

Answer 1

Yes.

Let $c_0 = 0$ and $c_i = \sum_{j=1}^i a_i$, (which can be done in linear time). Now the problem becomes -- find $0\le i < k\le n$ such that for all $i\le j<k$ we have $c_i\le c_j \le c_k$ that maximizes $k-i$. This can be found in a single sweep. (I'll let you work out the details.)

For the problem actually asked: We want the longest subsequence that begins and ends with 1 and each of the prefix and suffix sums is nonnegative. First note that all $a_i=1$ are included as including it will only increase the prefix and suffix sums. In particular $b_1=a_1$ and $b_k=a_n$. We can construct $(b)$ in two passes. First pass from $i=1$ to $n$ selecting every $a_i$ such that either $a_i = 1$ or $a_i=-1$ and the prefix condition is not violated in our subsequence (we are greedily selecting everything subject to the prefix condition). Now pass backwards through the subsequence discarding elements that violate the suffix condition.

Note that since all of the $a_i=1$ are in $(b)$ the sum of $(b)$ is just the count of $a_i=b_j=1$ minus the count of the $b_j=-1$ and so is twice the count of $a_i=1$ minus the length of $(b)$, a function of the length. So any other subsequence satisfying the conditions having the same length will have the same sum.