using System;

using System.Collections.Generic;

​

public class Program

{

    /*

    Given an array of numbers, find the length of the longest increasing subsequence in the array. The subsequence does not necessarily have to be contiguous.

​

For example, given the array [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], the longest increasing subsequence has length 6: it is 0, 2, 6, 9, 11, 15.

    */

    public static int longestIncreasingSubSequense(int[] array)

    {

        int longest = 0;

        helper(array, 0, new List<int>(), ref longest);

        return longest;

    }

​

    public static void helper(int[] array, int i, List<int> slate, ref int longest)

    {

        if (i == array.Length)

        {

            longest = Math.Max(longest, slate.Count);

            return;

        }

​

        int num = array[i];

        if (slate.Count == 0 || slate[slate.Count - 1] < num)

        {

            slate.Add(num);

            helper(array, i + 1, slate, ref longest);

            slate.RemoveAt(slate.Count - 1);

        }

​

        helper(array, i + 1, slate, ref longest);

    }

    public static int longestIncreasingSubSequenceOptimized(int[]array){

        int max=0;

        int[] cache = new int[array.Length];

        for(int i=0;i<cache.Length;i++){ cache[i]=1;}

        for(int i=1;i<cache.Length;i++){

            for(int j=0;j<i;j++){

                if(array[i]>array[j]&&cache[i]<=cache[j]){

                    cache[i]=cache[j]+1;

                    max=Math.Max(max,cache[i]);

                }

            }

        }

        return max;

    }

​

    public static void Main()

    {

        // brute force 2^n

        Console.WriteLine(longestIncreasingSubSequense(new int[]{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}));

        Console.WriteLine(longestIncreasingSubSequenceOptimized(new int[]{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}));

    }

}