fork(4) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. #include <iostream>
  4. #include <vector>
  5.  
  6.  
  7. void prt(vector<int>& arr, string msg = "") {
  8. 	cout << msg << " ";
  9. 	for  (auto i: arr) {
  10. 		cout << i << " ";
  11. 	}
  12. 	cout << endl;
  13. }
  14.  
  15.  
  16. void calc_LIS(vector<int>& D) {
  17. 	vector< vector<int> > L(D.size());  // The longest increasing subsequence ends with D[i]
  18.  
  19.    L[0].push_back(D[0]);
  20.  
  21. 	for (int i=1; i<D.size(); i++) {
  22. 		for(int j=0; j<i; j++) {
  23. 			if ( (D[j] < D[i]) && ( L[i].size() < L[j].size() ) ) {
  24. 				L[i] = L[j];  				
  25. 			}         
  26. 		}
  27.       L[i].push_back(D[i]);
  28. 	}
  29.  
  30. 	for (auto x: L) {
  31. 		prt(x);
  32. 	}
  33.  
  34. }
  35.  
  36. int main() {
  37. 	int a[] = {3, 4, 6, 4, 5, 1};
  38. 	vector<int> arr(a, a + sizeof(a)/sizeof(a[0]));
  39.  
  40. 	//prt(arr, "Data In:");
  41. 	calc_LIS(arr);
  42.  
  43. 	return 0;
  44. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 3 
 3 4 
 3 4 6 
 3 4 
 3 4 5 
 1
https://ideone.com/lOrktE
DP LIS
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!