Q25

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A[0:n-1]$ is given below. Let $L_i$, denote the length of the longest monotonically increasing sequence starting at index $i$ in the array. Initialize $L_{n-1} = 1$. For all $i$ such that $0 \leq i \leq n-2$ $L_i = \begin{cases} 1+ L_{i+1} & \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases}$ Finally, the length of the longest monotonically increasing sequence is $\text{max} \:(L_0, L_1, \dots , L_{n-1}).$ Which of the following statements is TRUE?