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 .
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 = 1;
For ( k going from 1 to n-1)
Compute L[k] using the above recurrence.
Index[k] = i;
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 = 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.
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.