4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The subsequence $b$ need not be contiguous. $\endgroup$ – Yuval Filmus Oct 8 '13 at 20:58
  • $\begingroup$ Sorry, i forgot about one case. The sum of $(b)$ must be biggest possible. Albo $b$ need not be contiguous. $\endgroup$ – John Cina Oct 8 '13 at 21:31
  • $\begingroup$ What about if $a_i \in -1,0,1$ ? It makes problem harder? $\endgroup$ – John Cina Oct 8 '13 at 21:37
  • $\begingroup$ According to your version of problem, how to do it in single sweep? Are you assumming that $c_i \geq c_{i-1}$ ? $\endgroup$ – John Cina Oct 8 '13 at 21:43
  • $\begingroup$ I missed that it need not be contiguous, I'll add that after dinner (that is a different problem). $\endgroup$ – Deinst Oct 8 '13 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.