Advertisement
Guest User

Leghosszabb növekvő részsorozat hossza

a guest
Dec 11th, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. /**
  6.  * Eljaras a sorozat beolvasasahoz
  7.  * @param a feltoltendo tomb
  8.  * @param n sorozat elemeinek szama
  9.  */
  10. void input(int a[], int &n) {
  11.     cout << "n: ";
  12.     cin >> n;
  13.     for(int i = 0; i < n; i++) {
  14.         cout << "a[" << i << "]: ";
  15.         cin >> a[i];
  16.     }
  17. }
  18.  
  19. /**
  20.  * Kiirja a leghoszabb reszsorozat hosszat
  21.  * @param n hossz
  22.  */
  23. void output(int n) {
  24.     cout<< "A leghoszabb reszsorozat hossza: "<< n;
  25. }
  26.  
  27. /**
  28.  * Megkapja egy tomb legnagyobb elemet
  29.  * @param a tomb
  30.  * @param n elemek szama
  31.  * @return legnagyobb elem
  32.  */
  33. int largest(int a[], int n) {
  34.     int max = a[0];
  35.     for(int i=1; i < n; i++) {
  36.         if(a[i] > max) {
  37.             max = a[i];
  38.         }
  39.     }
  40.     return max;
  41. }
  42.  
  43. /**
  44.  * Feltoltjuk a segedtombot aszerint, hogy az a tomb i. eleme
  45.  * a sorozat i. elemetol szamolt leghoszabb reszsorozat hossza legyen
  46.  * @param a tomb
  47.  * @param b segedtomb
  48.  * @param n elemek szama
  49.  */
  50. void fill(int a[], int b[], int n) {
  51.     for(int i = n - 1; i >= 0; i--) {
  52.         b[i] = 0;
  53.         for(int j = i+1; j<n; j++) {
  54.             if(a[i] < a[j] && b[i] < b[j]) {
  55.                 b[i] = b[j];
  56.             }
  57.         }
  58.         b[i]++;
  59.     }
  60. }
  61.  
  62. int main() {
  63.     /**
  64.      * A sorozatot tartalmazo tomb
  65.      */
  66.     int a[100];
  67.     /**
  68.      * Segedtomb, mely segitsegevel megkapjuk a hosszt
  69.      */
  70.     int b[100];
  71.     /**
  72.      * A sorozat elemeinek szama
  73.      */
  74.     int n;
  75.  
  76.  
  77.     input(a, n);
  78.     fill(a, b, n);
  79.     output(largest(b, n));
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement