Given a sequence S x0 x1 x2 xn1 of numbers describe an

Given a sequence S = (x0, x1, x2, . . . , xn1) of numbers, describe an O(n2)- time algorithm for finding a longest subsequence T = (xi0 , xi1 , xi2 , . . . , xik1 ) of numbers, such that ij < ij+1 and xij > xij+1 . That is, T is a longest decreas- ing subsequence of S.

Solution

Hi, we can use Dynamic Programming Concept.

Please find my function that computes in bottom-up manner.

/* list() returns the length of the longest decreasing subsequence in arr[] of size n */
int list(int arr[],int n)
{
int list[] = new int[n];
int i,j,max = 0;

/* Initialize list values for all indexes */
for ( i = 0; i < n; i++ )
list[i] = 1;

/* Compute optimized list values in bottom up manner */
for ( i = 1; i < n; i++ )
for ( j = 0; j < i; j++ )
if ( arr[i] < arr[j] && list[i] < list[j] + 1)
list[i] = list[j] + 1;

/* Pick maximum of all values */
for ( i = 0; i < n; i++ )
if ( max < list[i] )
max = list[i];

return max;
}

1. list[i] < list[j] + 1, to update only if the new value will give the higher value than what exists

2. if if arr[i] < arr[j] and list[i]< list[j] + 1 condition is true, you got a sub-sequence which has length 1 higher than the list found till arr[0] to arr[i-1]

Time Complexity: O(n^2)