Advertisement
skb50bd

Longest Decreasing Subsequence

Oct 29th, 2016
230
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <string>
  4. #include <sstream>
  5. #define SIZE 100
  6. #define TAB 3
  7.  
  8. using namespace std;
  9.  
  10. void LDS (int A[], int C[], int N) {
  11.     C[0] = 1;
  12.     int max;
  13.     for (int i = 1; i < N; i++) {
  14.         max = 0;
  15.         for (int j = i - 1; j >= 0; j--)
  16.             if (C[j] > max && A[j] > A[i])
  17.                 max = C[j];
  18.         C[i] = 1 + max;
  19.     }
  20. }
  21.  
  22. int findLDS (int A[], int B[], int C[], int N) {
  23.     int max = 0;
  24.     int pos = 0;
  25.     for (int i = N - 1; i >= 0; i--)
  26.         if (C[i] > max) {
  27.             max = C[i];
  28.             pos = i;
  29.         }
  30.     int n = max;
  31.     for (int i = pos; i >= 0; i--)
  32.         if (C[i] == n)
  33.             B[--n] = A[i];
  34.  
  35.     return max;
  36. }
  37.  
  38.  
  39. void printSequence (int B[], int n) {
  40.     for (int i = 0; i < n; i++)
  41.         cout << B[i] << " ";
  42.     cout << endl;
  43. }
  44.  
  45. void printArrays (int A[], int C[], int N) {
  46.     cout << "A: ";
  47.     for (int i = 0; i < N; i++)
  48.         cout << setw(TAB) << A[i];
  49.     cout << endl;
  50.     cout << "C: ";
  51.     for (int i = 0; i < N; i++)
  52.         cout << setw(TAB) << C[i];
  53.     cout << endl;
  54. }
  55.  
  56. int main () {
  57.     string line;
  58.     cout << "Enter the Array: ";
  59.     getline(cin, line);
  60.     istringstream iss(line);
  61.  
  62.     int N, n;
  63.     int A[SIZE];
  64.     int B[SIZE];
  65.     int C[SIZE];
  66.  
  67.     for (N = 0; iss >> line; N++)
  68.         stringstream(line) >> A[N];
  69.  
  70.     LDS (A, C, N);
  71.     n = findLDS(A, B, C, N);
  72.     cout << "Length of Longest Decreasing Subsequence: " << n << endl;
  73.     cout << "Longest Decreasing Subsequence: ";
  74.     printSequence(B, n);
  75.     printArrays(A, C, N);
  76.  
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement