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 <i_1, i_2, \ldots, i_k> (where i_1 < \ldots <I_k), 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.

———–


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: