1

We have a sequence $A$ of size $n$, where each element $A_i \in \{-1,0,1\}$. In each operation we can increase $A_{i+1}$ by $A_i$. The goal is to make the sequence non-decreasing i.e. $A_1 \leq A_2 \leq \dots \leq A_n $ with the minimum number of operations. Assume that $A$ is a sequence which can be always made non decreasingly.

Is my assumption true, that at the end of all operations, every element $A_i \in \{-1,0,1\}$? And if yes, how do we prove it?

Gary
  • 271
  • Suppose $A_1=A_2=\cdots=A_{n-1}=0$, and $A_n=-1$. How do you make this non-decreasing using these operations? – vadim123 Feb 14 '14 at 22:41
  • My apology. I should have told you that you must assume that the sequence can be made non decreasingly. – Gary Feb 14 '14 at 22:43

0 Answers0