Solve the Longest Array Subsequence program in C#

Question

The question is already asked in SO:

Longest increasing subsequence

but the solution is in Python.

Here is my C# version

private static int longestSeq(int[] input1)
            {                
                int counter = 0;
                int i = 0;
                int x = 0;
                bool flag = true;

                if (input1.Length == 0) return 0;
                if (input1.Length == 1) return 1;

                while (i != input1.Length-1)
                {
                     if (flag)x= input1[i];
                    int y = input1[i + 1];
                    if (x < y) { counter++; flag = true; }
                    else { if (flag) { x = input1[i]; flag = !flag; } }
                    i++;
                }

                return counter+1;
            }

But it is not working for

int[] input1 = new int[] { 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15 };

The expected output is 6 but I am getting 5.

2 questions

a) What is that i am missing?

b) How can I optimize my program

Answer 1

I've just invented a superfast ;-) algorithm for at least this case now (it still requires dynamic indexing optimization but it works):

My algorithm works with a tolerance/distance that specifies how far a number can be from its sorted index. Based on the image that I drew:

and it turned out that at least here, the distance of 2 gives us the correnct results (= the numbers that lie closest to their sorted positions). I have to invesitigate it more but it seems do the work.

There can be two cases (that I can think of) how we find the increasing sequence:

• 1st case - the tolerance is positive. This gives us a result where we get: 0, 2, 6, 9 , 11, 15
• 2nd case - the tolerance is negative. This would give us: 0, 4, 6, 9 , 13, 15

I saw in the linked question another result like this: 0, 2, 6, 9 , 13, 15 but I think it's wrong and inconsistent if you compare it with the two cases and the image because if we take the 2 we cannot take the 13 later. We had to take the 11 like we took the 2 at the beginning of the array. Compare 4, 12, 2 and 13, 3, 11.

Here's the code:

class Program
{
    static void Main(string[] args)
    {
        //int[] seq = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
        //int[] seq = new int[] { 0, 8, 4, 2, 12, 10, 6, 14, 1, 9, 5, 7, 3, 11, 15, 13 };
        //int[] seq = new int[] { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 16, 7, 15, 11 };
        //int[] seq = new int[] { 3, 1, 2, 5, 4, 8, 6 };
        int[] seq = new int[] { 6, 3, 4, 8, 10, 5, 7, 1, 9, 2 };
        var result = longestSeq3(seq);
    }

    private static List<int> longestSeq3(int[] seq)
    {
        int maxDist = 2;
        List<int> result = new List<int>();

        for (int i = 0; i < seq.Length; i++)
        {
            int current = seq[i];
            int dist = Math.Abs(i - current);
            if (dist >= 0 && dist <= maxDist)
            {
                if (result.Count > 0 && current <= result.Last())
                {
                    continue;
                }
                result.Add(current);
            }
        }

        return result;
    }
}