陣列中最長的子序列

Question

我想用列表解決我的任務，我知道我非常接近解決它，但我現在卡住了。代碼中的某些內容不正確，我無法弄清楚它是什麼。你可以請看看和幫助：

 /* 
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

我不知道如果一個詳盡的搜索適合您的情況，但這會爲你工作嗎？

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

我沒有按照代碼，我只是測試你的應用程序。

這是我第一次輸入：5

然後我進入這5個輸入2,4,6,8,10等等

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

當它來到最後一行它給了我ArguementOutOfRangeException(Index was out of range. Must be non-negative and less than the size of the collection.)因爲它試圖獲取arr [item]而item是6，所以它試圖獲取arr[6]，這不存在。

Answer 3

我解決了！非常感謝您的支持。我是一個開始，我不能夠使用和理解更難的東西，所以這裏是我所做的白衣我已經知道的東西：

/* 
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]); 
     } 
    } 
}