Advertisement
TeMePyT

Untitled

May 26th, 2018
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.98 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. namespace Longest_Increasing_Subsequence
  8. {
  9. class Program
  10. {
  11. static void Main(string[] args)
  12. {
  13. List<int> numbers = Console.ReadLine().Split(' ').Select(int.Parse).ToList();
  14.  
  15. int[] len = new int[numbers.Count];
  16. int[] prev = new int[numbers.Count];
  17.  
  18. for (int i = 0; i < numbers.Count; i++)
  19. {
  20.  
  21. int biggestLen = 0;
  22. int biggestIndex = -1;
  23.  
  24. for (int j = i; j >= 0; j--)
  25. {
  26. if (numbers[j] < numbers[i] && len[j]>=biggestLen)
  27. {
  28. biggestLen = len[j];
  29. biggestIndex = j;
  30.  
  31. }
  32.  
  33. }
  34. prev[i] = biggestIndex;
  35. len[i] = GetLen(i, numbers, prev);
  36. }
  37.  
  38. int index = len.ToList().FindIndex(l => l == len.Max());
  39. List<int> sequence = GetSequence(index, numbers, prev);
  40. Console.WriteLine(string.Join(" ", sequence));
  41. }
  42.  
  43. private static List<int> GetSequence(int index, List<int> numbers, int[] prev)
  44. {
  45. if(prev[index]<0)
  46. {
  47.  
  48. return new List<int> { numbers[index] } ;
  49. }
  50. else
  51. {
  52. List<int> list = GetSequence(prev[index], numbers, prev);
  53. list.Add(numbers[index]);
  54. return list;
  55. }
  56. }
  57.  
  58. private static int GetLen(int i, List<int> numbers, int[] prev)
  59. {
  60. if (prev[i]<0)
  61. {
  62. return 1;
  63. }
  64. else
  65. {
  66. int a = GetLen(prev[i], numbers, prev);
  67. return a + 1;
  68. }
  69. }
  70. }
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement