la plus longue séquence dans le tableau

Question

Je tente de résoudre ma tâche à l'aide d'une liste et je sais que je suis très proche de la solution, mais je suis coincé maintenant. Quelque chose ne va pas dans le code et je n'arrive pas à comprendre ce que c'est. Pourriez-vous s'il vous plaît jeter un oeil et aider:

 /* 
Write a program that reads an array of integers and removes from it a minimal number of elements in such way that the 
remaining array is sorted in increasing order. Print the remaining sorted array. 
Example: {6, 1, 4, 3, 0, 3, 6, 4, 5}  {1, 3, 3, 4, 5} 
*/ 
using System; 
using System.Collections.Generic; 

class RemoveMinimalElements 
{ 

    static void Main() 
    { 
     int n; 
     n = int.Parse(Console.ReadLine()); 
     List<int> arr = new List<int>(); 
     List<int> sorted = new List<int>(); 
     int maxSubsetLenght = 0; 

     for (int i = 0; i < n; i++) 
     { 
      arr.Add(int.Parse(Console.ReadLine())); 
     } 


     for (int i = 1; i <= (int)Math.Pow(2, n) - 1; i++) 
     { 
      int tempSubsetLenght = 0; 
      string tempString = ""; 
      List<int> temp = new List<int>(); 


      for (int j = 1; j <= n; j++) 
      { 
       int andMask = i & (1 << j); 
       int bit = andMask >> j; 

       if (bit == 1) 
       { 
        temp.Add(arr[n - 1 - j]); 
        tempSubsetLenght++; 
       } 
       if (tempSubsetLenght > maxSubsetLenght) 
       { 
        maxSubsetLenght = tempSubsetLenght; 

        for(int k =1; k < temp.Count; k ++) 
        { 
         if (temp[k] >= temp[k - 1]) 
         { 
          sorted = temp; 
         } 
        } 
       } 
      } 
     } 

     for (int i = sorted.Count - 1; i > 0; i--) 
     { 
      Console.WriteLine(sorted[i]); 
     } 
    } 
} 

Answer 1

Je ne sais pas si une recherche exhaustive est adaptée à votre cas, mais ce travail pour vous?

static void Main(string[] args) 
     { 
      int[] input = new[] { 6, 1, 4, 3, 0, 3, 6, 4, 5 }; 
      int[] expectedOutput = new[] { 1, 3, 3, 4, 5 }; 

      int[] solution = TryGetSolution(input); 

      Console.WriteLine("Input: " + FormatNumbers(input)); 
      Console.WriteLine("Expected Output: " + FormatNumbers(expectedOutput)); 
      Console.WriteLine("Output: " + FormatNumbers(solution)); 
      Console.ReadLine(); 
     } 

     private static string FormatNumbers(int[] numbers) 
     { 
      return string.Join(", ", numbers); 
     } 

     private static int[] TryGetSolution(int[] input) 
     { 
      return TryWithoutAnyItem(input); 
     } 

     private static int[] TryWithoutAnyItem(int[] items) 
     { 
      return Enumerable.Range(0, items.Length) 
          .Select(i => TryWithoutItem(items, i)) 
          .Where(solution => solution != null) 
          .OrderByDescending(solution => solution.Length) 
          .FirstOrDefault(); 
     } 

     private static int[] TryWithoutItem(int[] items, int withoutIndex) 
     { 
      if (IsSorted(items)) return items; 
      var removed = items.Take(withoutIndex).Concat(items.Skip(withoutIndex + 1)); 
      return TryWithoutAnyItem(removed.ToArray()); 
     } 

     private static bool IsSorted(IEnumerable<int> items) 
     { 
      return items.Zip(items.Skip(1), (a, b) => a.CompareTo(b)).All(c => c <= 0); 
     } 
    } 

Answer 2

Je n'ai pas suivi le code, je viens de tester votre application.

Ceci est ma première entrée: 5.

Puis je suis entré dans ces 5 entrées 2,4,6,8,10 si

arr = {2,4,6,8,10}; 

Et quand il est venu à la dernière ligne, il m'a donné le ArguementOutOfRangeException(Index was out of range. Must be non-negative and less than the size of the collection.) parce qu'il essayait de chercher [point] arr et article est 6 donc il essaie de chercher arr[6] qui n'existe pas.

Answer 3

Je l'ai résolu! Merci beaucoup pour votre soutient. Je suis un débutant et je ne suis pas capable d'utiliser et de comprendre des choses plus difficiles encore si voici ce que j'ai fait avec les choses que je connais déjà:

/* 
Write a program that reads an array of integers and removes from it a minimal number of elements in such way that the 
remaining array is sorted in increasing order. Print the remaining sorted array. 
Example: {6, 1, 4, 3, 0, 3, 6, 4, 5}  {1, 3, 3, 4, 5} 
*/ 
using System; 
using System.Collections.Generic; 

class RemoveMinimalElements 
{ 
    static bool CheckAscending(List<int> list) 
    { 
     bool ascending = true; 

     for (int i = 0; i < list.Count - 1; i++) 
     { 
      if (list[i] > list[i + 1]) 
      { 
       ascending = false; 
      } 
     } 

     return ascending; 
    } 

    static void Main() 
    { 
     int n; 
     n = int.Parse(Console.ReadLine()); 
     List<int> arr = new List<int>(); 
     List<int> sorted = new List<int>(); 
     int maxSubsetLenght = 0; 

     for (int i = 0; i < n; i++) 
     { 
      arr.Add(int.Parse(Console.ReadLine())); 
     } 


     for (int i = 1; i <= (int)Math.Pow(2, n) - 1; i++) 
     { 
      int tempSubsetLenght = 0; 
      List<int> temp = new List<int>(); 


      for (int j = 1; j <= n; j++) 
      { 
       if (((i >> (j - 1)) & 1) == 1) 
       { 
        temp.Add(arr[j - 1]); 
        tempSubsetLenght++; 
       } 

      } 

      if ((tempSubsetLenght > maxSubsetLenght) && (CheckAscending(temp))) 
      { 
       sorted = temp; 
       maxSubsetLenght = tempSubsetLenght; 
      } 
     } 

     for (int i = 0; i < sorted.Count; i++) 
     { 
      Console.WriteLine(sorted[i]); 
     } 
    } 
}