What The Threshold Remembers

One standard recurrence for longest increasing subsequence walks the array asking whether each element can be appended after the last one already chosen. Writing ii for the position of that last chosen element and jj for the candidate:

LISbigger(i,j)={0j>nLISbigger(i,j+1)A[i]≥A[j]max⁡(LISbigger(i,j+1), 1+LISbigger(j,j+1))otherwise\text{LISbigger}(i,j) = \begin{cases}0 & j > n \\text{LISbigger}(i, j+1) & A[i] \ge A[j] \\max\big(\text{LISbigger}(i, j+1),\ 1 + \text{LISbigger}(j, j+1)\big) & \text{otherwise}\end{cases}

A student memoizes on jj alone, reasoning that ii is just where the recursion came from. What does dropping ii destroy?

A

The array bound nn, which the base case compares against.

B

The value the next element has to beat, so an answer computed under one predecessor gets served back under a different one.

C

The length of the subsequence built so far, which the recurrence needs in order to report a maximum.

D

Nothing, as long as the array is scanned left to right, because ii is always j−1j - 1.