Longest increasing subsequence problem (Dynamic Programming)

The input consists of two sequences ~x = x1, . . . , xn and ~y = y1, . . . , ym. The goal is to find 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


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

Post a Comment

0 Comments

Close Menu