The "Smooth Factor" in a number sequence

Question

I'm trying to figure out a programming problem that has mathematical foundations.

The problem says:

---

For an array $$a = a_1, a_2, ..., a_n$$ of values, the smooth factor of $$a$$ is the length of a longest subarray $$a_p, ..., a_q$$ of $$ a (1 \leq p \leq q \leq n)$$ such that there is at most one $$i (p < i \leq q)$$ such that $$a_{i−1} > a_i$$where < is some fixed order on the values in $a$. The higher the smooth factor, the more effective the smooth phase is.

For example, under the natural order of integer numbers, for the array $1, 2, 3$ the smooth factor is $3$ and for the array $1, 2, 1, 2, 1, 2, 3, 1$ the smooth factor is $5$. In the first case the entire array serves as a witness and in the second case the witness is $1, 2, 1, 2, 3$.

---

I understand this problem is: find the largest sequence of consecutive numbers in ascending order of the set of numbers that give me.

However the example, two "$1, 2, 1, 2, 3$" escapes from this sequence.

Can they give me an idea?

---

Annex another set of examples:

1, 1, 1, 1, 2, 2, 3, 3 = 8

3, 4, 5, 7, 6, 8, 9, 2, 1 = 7

1, 1, 1, 1, 1, 1, 1, 1, 2 = 9

Answer 1

"the largest sequence of consecutive numbers in ascending order" or two such sequences concatenated with only one "decrease" between them, according to this:

the smooth factor of $a$ is the length of a longest subarray $a_p, ..., a_q$ of $ a (1 \leq p \leq q \leq n)$ such that there is at most one $i (p < i \leq q)$ such that $a_{i−1} > a_i$

"at most one" is "1 or 0". So,
1. purely non-descending sequence does
2. non-descending sequence with only 1 "break" (labeled "&" below)
E.g. 1,2 & 1,2,3 and
$1\le 1\le 1\le 1\le 2\le 2\le 3\le 3$
$3\le 4\le 5\le 7\le 6\le 8\le 9\& 2$
$1\le 1\le 1\le 1\le 1\le 1\le 1\le 1\le2$ in the cases above.

Answer 2

The following algorithm should work in linear time:

• Step 1: Partition $a$ into $k$ subarrays ($b_1, \ldots, b_k$), each of which are in nondescending order (either stays the same or increases). Store all the subarrays into a list $L$ of witness candidates.

• Step 2: Peform $k - 1$ merges between consecutive subarrays ($b_1b_2, b_2b_3, \ldots, b_{k-1}b_k$) and append each one to $L$.

• Step 3: Scan $L$ and return the longest.

For example, consider: $$ a = 1, 2, 1, 3, 1, 2, 1, 2, 3, 2, 1, 2 $$

• Step 1: We get: \begin{align*} b_1 &= 1, 2 \\ b_2 &= 1, 3 \\ b_3 &= 1, 2 \\ b_4 &= 1, 2, 3 \\ b_5 &= 2 \\ b_6 &= 1, 2 \end{align*}

• Step 2: Our list of $6 + (6 - 1) = 11$ candidates is: $$ L = [b_1, b_2, b_3, b_4, b_5, b_6, b_1b_2, b_2b_3, b_3b_4, b_4b_5, b_5b_6] $$

• Step 3: Our witness is the longest candidate in $L$: $$ b_3b_4 = 1, 2, 1, 2, 3 $$ Hence, its smooth factor is $5$.