Advertisement
AlexandraCatana

Untitled

Jun 26th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.92 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. int n, a[1001], T[1001], i, j, L[1001];
  6.  
  7. void printSol(int index) {
  8. if ( T[index] != 0 ) {
  9. printSol(T[index]);
  10. }
  11.  
  12. printf("%d ", index);
  13. }
  14.  
  15. int main() {
  16.  
  17. freopen("sclm.in", "r", stdin);
  18. freopen("sclm.out", "w", stdout);
  19.  
  20. scanf("%d", &n);
  21.  
  22. for ( i = 1; i <= n; i++ ) {
  23. scanf("%d", &a[i]);
  24. }
  25.  
  26. L[1] = 1;
  27. T[1] = 0;
  28.  
  29. int indexSol = 1, maxLength = 1;
  30.  
  31. for ( i = 2; i <= n; i++ ) {
  32. L[i] = 1;
  33. T[i] = 0;
  34.  
  35. for ( j = 1; j < i; j++ ) {
  36. if ( a[i] >= a[j] && L[j] + 1 > L[i] ) {
  37. L[i] = L[j] + 1;
  38. T[i] = j;
  39. }
  40. }
  41.  
  42. if ( L[i] > maxLength ) {
  43. maxLength = L[i];
  44. indexSol = i;
  45. }
  46. }
  47.  
  48. printf("%d\n", maxLength);
  49.  
  50. printSol(indexSol);
  51.  
  52. return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement