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

Leave a Reply

Your email address will not be published. Required fields are marked *