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

February 15, 2011 Leave a comment

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 ), we want that .

Solution.

Let us define to be the length of the longest non-decreasing subsequence ending at index .

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

.

We can do the above step in time.

——

Let us now look at computing values.

We have the following recurrence:

.

In the above equation, the maximum is taken over all indices for which . (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 , .

——-

Now that we have the recurrence, we can compute the values in a bottom up fashion iteratively. We will also keep a record of the index (as defined above) for each 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 time.

– Computing OPT from L values takes time.

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

———–