Advertisement
Guest User

Untitled

a guest
Oct 15th, 2019
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.93 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6. long long n;
  7. long long L[1001], a[1001], truoc[1001], ketqua[1001], ans;
  8.  
  9. cin >> n;
  10. for (int i = 1; i <= n; i++)
  11. cin >> a[i];
  12.  
  13. L[0] = 0;
  14. a[0] = -100000000;
  15.  
  16. for (int i = 1; i <= n; i++)
  17. {
  18. int j = 0;
  19. for (int k = 0; k <= i - 1; k++)
  20. {
  21. if (a[k] <= a[i] && L[k] > L[j])
  22. {
  23. j = k;
  24. }
  25. }
  26. L[i] = L[j] + 1;
  27. truoc[i] = j;
  28. }
  29.  
  30. ans = 1;
  31. for (int i = 2; i <= n; i++)
  32. if (L[i] > L[ans])
  33. {
  34. ans = i;
  35. }
  36. // for (int i = 1; i <= n; i++)
  37. // {
  38. // cout << L[i] << " ";
  39. // cout << endl;
  40. // }
  41. cout << L[ans] << endl;
  42. long long dem = 0;
  43. while (truoc[ans] > 0)
  44. {
  45. dem++;
  46. ketqua[dem] = a[ans];
  47. ans = truoc[ans];
  48. }
  49.  
  50. // for (int i = 1; i <= n; i++)
  51. // {
  52. // cout << truoc[i] << " ";
  53. // cout << endl;
  54. // }
  55.  
  56. dem++;
  57. ketqua[dem] = ans;
  58. for (int i = dem; i >= 1; i--)
  59. cout << ketqua[i] << " ";
  60.  
  61.  
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement