# Longest non-decreasing subsequence : More on dynamic programming – 1

Question. We are given an array A of n integers. We wish to find the longest subsequence such that if the indices in the subsequence are $$ (where $i_1 < \ldots ), we want that $A[i_1] \leq \ldots A[i_k]$.

Solution.

Let us define $L(k)$ to be the length of the longest non-decreasing subsequence ending at index $k$.

Now if $OPT$ denotes the length of the longest non-decreasing subsequence in A, then we have that:

$OPT = \max_{0 \leq k \leq n-1} L(k)$.

We can do the above step in $O(n)$ time.

——

Let us now look at computing $L(k)$ values.

We have the following recurrence:

$L(k) = 1 + \max_i L(i)$.

In the above equation, the maximum is taken over all indices $0 \leq i \leq k-1$ for which $A[i] \leq A[k]$. (i.e. for which we can safely add A[k] to the already existing longest non-decreasing subsequence ending at i.)

In case there exists no such index $i$, $L(k) = 1$.

——-

Now that we have the recurrence, we can compute the $L(k)$ values in a bottom up fashion iteratively. We will also keep a record of the index $i$ (as defined above) for each $L(k)$ that we compute. This will help us when we want to reconstruct the optimal solution.

—–

Pseudo-code for computing L(k) values:

L[0] = 1;

For ( k going from 1 to n-1)

Compute L[k] using the above recurrence.

Index[k] = i;

End.

——

Coding in C/ C++ would give us:

int L[n], Index[n], OPT = 0, final_index = -1;

//final_index is the index of the last term in the optimal subsequence. (Note: there can be //more that one optimal subsequence. We consider one of them.

L[0] = 1;

for (int k=1; k<n; k++)

{

int temp_max = 0, temp_index = k; //default values of L[k]-1 and Index[k].

for (int i = 0; i<k; i++)

{

if (A[i] <= A[k]) //it is safe to include A[k] in this subsequence.

{

if (L[i] > temp_max)

{

temp_max = L[i];

temp_index = i;

}

}

}

L[k] = 1 + temp_max;

Index[k] = temp_index;

}

//now, to compute OPT.

for (k=0; k<n; k++)

{

if (L[k] > OPT)

{

OPT = L[k];

final_index = k;

}

}

//Now, we construct the optimal subsequence using our Index array.

// We do so recursively using a function Print_Solution.

// void Print_Solution ( int Index [ ], int n);

void Print_Solution ( int Index [ ], int n, int final_index)

{

int prev_index = Index[final_index];

if (prev_index == final_index) //this is where the subsequence begins; end recursion.

return;

Print_Solution (Index, n, prev_index);

cout << A [final_index] << endl;

}

———–

Analysis of the algorithm:

– Computing the L and Index arrays takes $O(n^2)$ time.

– Computing OPT from L values takes $O(n)$ time.

– Constructing the optimal subsequence from Index values takes O(n) time.

———–