public static string FindLcs (int[] a, int[] b)
    {
        var cache = new int[b.Length + 1, a.Length + 1];
        InitCache(cache);
        FillDpTable(cache, a, b);
        return ConstructLcsString(a, cache);
    }
    
    private static void InitCache(int[,] cache)
    {
        for (int i = 0; i < cache.GetLength(0); i++)
        {
            cache[i, 0] = 0;
        }

        for (int i = 0; i < cache.GetLength(1); i++)
        {
            cache[0, i] = 0;
        }
    }
    
    private static void FillDpTable(int[,] cache, int[] row, int[] col)
    {
        for (int i = 1; i <= col.Length; i++)
        {
            for (int j = 1; j <= row.Length; j++)
            {
                if (col[i - 1] == row[j - 1])
                {
                    cache[i, j] = 1 + cache[i - 1, j - 1];
                }
                else
                {
                    cache[i, j] = Math.Max(cache[i - 1, j], cache[i, j - 1]);
                }
            }
        }
    }

    private static string ConstructLcsString(int[] row, int[,] cache)
    {
        string result = "";
        int i = cache.GetLength(0) - 1;
        int j = cache.GetLength(1) - 1;

        while (i > 0 && j > 0)
        {
            if (cache[i, j - 1] != cache[i, j] && cache[i - 1, j] != cache[i, j])
            {
                result = row[j - 1] + " " + result;
                i--;
                j--;
            }
            else if (cache[i - 1, j] == cache[i, j])
            {
                i--;
            }
            else
            {
                j--;
            }
        }

        return result.Trim();
    }