Solve the Longest Array Subsequence program in C#

Question

The question is already asked in SO:

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

Does the longest sequence list elements that is not smaller than the last element? — Hayden, Dec 29 '14 at 07:39
If it is port of that python version - it's very badly ported. This algorithm is slightly different than solution in your link. — , Dec 29 '14 at 07:53
You made the assumption that the first sequence of `x < y` is always correct (with your code above, it will return 5 because it evaluates 0, 8, 12, 14, 15 instead of 0, 2, 6, 9, 13, 15). — Hayden, Dec 29 '14 at 08:05
@Hayden the result `0, 2, 6, 9, 13, 15` is invalid, it should be either `0, 2, 6, 9, 11, 15` or `0, 4, 6, 9, 13, 15` because the 4 & 2 and the 13 & 11 in your result are inconsistent. See the image in my answer. First you take the smaller subsequent number and the other time the greather one? It's very confusing. — t3chb0t, Dec 29 '14 at 10:28
@t3chb0t How is my evaluation invalid? The OP is calculating an increasing scattered subsequence (http://mathworld.wolfram.com/LongestIncreasingScatteredSubsequence.html) and I don't see how my result is invalid? What are you talking about when you say that "the 4 & 2 and the 13 & 11 are inconsistent"? — Hayden, Dec 29 '14 at 12:13

t3chb0t · Accepted Answer · 2014-12-29T12:41:49.197

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:

enter image description here

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;
    }
}

Solve the Longest Array Subsequence program in C#

1 Answers1