# Longest increasing subsequence problem (Dynamic Programming)

The input consists of two sequences ~x = x1, . . . , xn and ~y = y1, . . . , ym. The goal is to ﬁnd a longest common subsequence of ~x and ~y

For example, let ~x and ~y be two DNA strings ~x = `TGACTA` and ~y = `GT GCATG`; n = 6 and m = 7. Then one common subsequence would be GT A. However, it is not the longest possible common subsequence: there are common subsequences T GCA, T GAT and `TGCT` of length 4

``````/// <summary>
/// Find largest increasing subsequence of given array
/// </summary>
public class LIS
{
private int[] _array;
private int _size;

public LIS(int[] arr, int size)
{
this._array = arr;
this._size = size;
}
void printLIS(int[] arr, int[] lis, int max, int n)
{
if (n < 0)
return;
if (lis[n] == max)
{
printLIS(arr, lis, max - 1, n - 1);
Console.Write(arr[n] + " ");
}
else
{
printLIS(arr, lis, max, n - 1);
}
}
public int FindList()
{
int[] best = new int[_size];
int[] prev = new int[_size];
int max = 0;
for (int i = 0; i < _size; i++)
{
best[i] = 1;
prev[i] = i;
}
for (int i = 1; i < _size; i++)
{
for (int j = 0; j < i; j++)
{
if (_array[i] > _array[j] && best[i] < best[j] + 1)
best[i] = best[j] + 1;
prev[i] = j; // prev[] is for backtracking the subsequence
}

}
for (int i = 0; i < _size; i++)
if (max < best[i])

max = best[i];
printLIS(_array, best, max, _size - 1);
return max;
}
}
``````