# Longest Increasing Subsequence Problem – Dynamic Programming

Given an array find a subsequence of a given array in which the array’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible

Example:

From below give array

`0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15`

a longest increasing subsequence is

`0, 2, 6, 9, 11, 15.`

This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not the only solution: for instance,

```
0, 4, 6, 9, 11, 15
0, 2, 6, 9, 13, 15
0, 4, 6, 9, 13, 15
```

are other increasing subsequences of equal length in the same input sequence.

#### Using Recursion

```
using System;
namespace LongestSubsequence{
class Program
{
static void Main()
{
var arr = new int[] {10, 22, 6, 30, 22, 50, 40, 30, 40};
var result =LongestSubsequenceRecurssion(arr, 0, arr.Length, 0);
Console.WriteLine($"The longest increasing subsequence is: {result}");
Console.ReadLine();
}
static int LongestSubsequenceRecurssion(int[] a, int current, int n, int previous)
{
if (current == n)
return 0;
if (a[current] <= previous)
return LongestSubsequenceRecurssion(a, current + 1, n, previous);
return Math.Max(1 + LongestSubsequenceRecurssion(a, current + 1, n, a[current]), LongestSubsequenceRecurssion(a, current + 1, n, previous));
}
}
}
```

#### Using Dynamic Programming:

```
using System;
namespace LongestSubsequence{
class Program
{
static void Main()
{
var arr = new int[] { 10, 22, 6, 30, 22, 50, 40, 30, 40 };
var result = LongestSubsequenceDynamicProgramming(arr);
Console.WriteLine($"The longest increasing subsequence is: {result}");
Console.ReadLine();
}
static int LongestSubsequenceDynamicProgramming(int[] arr)
{
var max = 0;
var tempArr = new int[arr.Length];
for (var i = 0; i < arr.Length; i++)
tempArr[i] = 1;
for (var i = 1; i < arr.Length; i++)
{
for (var j = 0; j < i; j++)
{
if (arr[i] > arr[j] && tempArr[i] < tempArr[j] + 1)
{
tempArr[i] = tempArr[j] + 1;
}
}
}
for (var i = 0; i < arr.Length; i++)
{
if (tempArr[i] > max)
max = tempArr[i];
}
return max;
}
}
}
```