using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace a_dalis
{
    class Program
    {
        static Int64 abc = 0;

        const int m = 10;
        const int n = 10;
        const int o = 10;

        static void Main(string[] args)
        {
            int[] X = new int[m + 1];
            int[] Y = new int[n + 1];
            int[] Z = new int[o + 1];

            int[,,] memoize = new int[m+2, n + 2,o+2];
            int i = 10;
            int j = 9;
            int k = 7;
            repeat(i,j,k, X,Y,Z, memoize);
            Console.WriteLine();
            Console.ReadLine();
        }

        static void repeat(int i, int j, int k, int[] X, int[] Y,int[] Z, int[,,] memoize)
        {
            initialize(memoize, X,Y,Z);

            Stopwatch stopwatch1 = new Stopwatch();
            Stopwatch stopwatch2 = new Stopwatch();

            stopwatch1.Start();
            Console.WriteLine("ATS:" + L1(i, j, k, X, Y, Z));
            Console.WriteLine("Atliktu operaciju skaicius: " + abc.ToString());
            abc = 0;
            stopwatch1.Stop();
            Console.WriteLine(stopwatch1.ElapsedMilliseconds);
            Console.WriteLine();

            stopwatch2.Start();
            Console.WriteLine("ATS: "+ tabulation(i, j, k, X, Y, Z,memoize));
            Console.WriteLine("Atliktu operaciju skaicius: " + abc.ToString());
            abc = 0;
            stopwatch2.Stop();
            Console.WriteLine(stopwatch2.ElapsedMilliseconds);

            Console.WriteLine();
        }
        static void initialize(int[,,] memoize,int[] X, int[] Y, int[] Z)
        {
            Random rnd = new Random();
            Random rnd1 = new Random();
            Random rnd2 = new Random();
            for (int i = 0; i <= m; i++)
            {
                X[i] = rnd.Next(0, 10);
            }
            for (int i = 0; i <= n; i++)
            {
                Y[i] = rnd1.Next(0, 10);
            }
            for (int i = 0; i <= o; i++)
            {
                Z[i] = rnd2.Next(0, 10);
            }
            for (int i=0;i<= m; i++)
            {
                for(int j=0;j<=n; j++)
                {
                    for(int z=0;z<= o;z++)
                        memoize[i, j,z] = 0;
                }
            }
        }

        static int L1(int i,int j, int k, int[] X, int[] Y, int[] Z)
        {
            abc++;
            if (X.Length == 0 || Y.Length == 0 || Z.Length == 0) return 0;
            if (i <= 0 || j <= 0 || k <= 0) return 0;
            if (X[i] == Y[j] && X[i] == Z[k]) return 1 + L1(i - 1, j - 1, k - 1, X, Y, Z);
            return Math.Max(Math.Max(L1(i-1, j, k, X, Y, Z), L1(i, j-1, k, X, Y, Z)), L1(i, j, k-1, X, Y, Z));
        }
        static int tabulation(int i, int j, int k, int[] X, int[] Y, int[] Z, int[,,] memoize)
        {
            for(int a = 0; a <= m; a++)
            {
                for(int b=0;b<= n; b++)
                {
                    for(int c=0;c<= o; c++)
                    {
                        abc++;
                        if(c==0 || b == 0 || a == 0)
                        {
                            memoize[a, b, c] = 0;
                        } else if(X[a]==Y[b] && X[a] == Z[c])
                        {

                            memoize[a, b, c] = memoize[a - 1, b - 1, c - 1] + 1;
                        } else
                        {
                           // Console.WriteLine(a.ToString() + b.ToString() + c.ToString());
                            memoize[a, b, c] = Math.Max(Math.Max(memoize[a-1, b, c], memoize[a, b-1, c]),memoize[a,b,c-1]);
                        }


                    }
                }
            }
            return memoize[i, j, k];
        }
    }
}