# 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, that is a sequence z1, . . . , zk that is a subsequence both of ~x and of ~y. Note that a subsequence is not always substring: if ~z is a subsequence of ~x, and zi = xj and zi+1 = xj 0, then the only requirement is that j 0 > j, whereas for a substring it would have to be j 0 = j + 1.For example, let ~x and ~y be two DNA strings ~x = T GACT A and ~y = GT GCAT G; 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 T GCT of length 4



.csharpcode, .csharpcode pre
{
font-size: small;
color: black;
font-family: Consolas, "Courier New", Courier, Monospace;
background-color: #ffffff;
/*white-space: pre;*/
}

.csharpcode pre { margin: 0em; }

.csharpcode .rem { color: #008000; }

.csharpcode .kwrd { color: #0000ff; }

.csharpcode .str { color: #a31515; }

.csharpcode .op { color: #0000c0; }

.csharpcode .preproc { color: #cc6633; }

.csharpcode .asp { background-color: #ffff00; }

.csharpcode .html { color: #800000; }

.csharpcode .attr { color: #ff0000; }

.csharpcode .alt
{
background-color: #f4f4f4;
width: 100%;
margin: 0em;
}

.csharpcode .lnum { color: #606060; }

/// <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;
}
}

Reactions