Решите Longest программу подпоследовательности массива в C#

Question

вопрос уже спросил SO:

Longest increasing subsequence

, но решение в Python.

Вот мой C# версии

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

Но это не работает для

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

Ожидаемый выход 6, но я получаю 5.

2 вопросы

a) Чего я чего-то не хватает?

б) Как я могу оптимизировать свою программу

Answer 1

Я только что придумал сверхбыстрого ;-) алгоритм по крайней мере этом сейчас (он по-прежнему требует оптимизации динамического индексирования, но она работает):

Мой алгоритм работает с tolerance/distance, который определяет, как далеко может быть номер из его отсортированного. На основе изображения, что я нарисовал:

, и оказалось, что по крайней мере здесь, расстояние 2 дает нам correnct результаты (= числа, которые лежат ближе всего к их отсортированных позиций). Мне нужно больше инвестировать, но, похоже, это работает.

Там может быть два случая (что я могу думать), как мы видим возрастающую последовательность:

• первый случай - толерантность является положительным. Это дает нам результат, когда мы получаем: 0, 2, 6, 9 , 11, 15
• 2-й корпус - отклонение отрицательное. Это дало бы нам: 0, 4, 6, 9 , 13, 15

я видел в связанном вопросе еще один результат, как этот: 0, 2, 6, 9 , 13, 15, но я думаю, что это неправильно и непоследовательно, если сравнить его с двумя случаями и изображения, потому что если мы возьмем 2 мы не можем возьмите 13 позже. Мы должны были взять 11, как мы взяли 2 в начале массива. Сравнить 4, 12, 2 и 13, 3, 11.

Вот код:

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