fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int N = 1e3 + 5;  
  8.  
  9. int n; 
  10. int a[N];  
  11. int dp[N]; // độ dài dãy con tăng dài nhất kết thúc tại i 
  12.  
  13. int memo[N];   
  14.  
  15. int f(int i) {
  16. 	int& ans = memo[i];   
  17. 	if (ans != -1) return ans;  
  18.  
  19. 	ans = 1;    
  20. 	for (int j = 1; j < i; j++) {
  21. 		if (a[i] > a[j]) ans = max(ans, f(j) + 1);   
  22. 	}
  23.  
  24. 	return ans;  
  25. }
  26.  
  27.  
  28. int main() {
  29. 	ios::sync_with_stdio(0); cin.tie(0);  	
  30. 	cin >> n;  
  31. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  32.  
  33. 	// // get về 
  34. 	// {
  35. 	// 	for (int i = 1; i <= n; i++) {
  36. 	// 		dp[i] = 1;   
  37. 	// 		for (int j = 1; j < i; j++) {
  38. 	// 			if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);  
  39. 	// 		}
  40. 	// 	}
  41. 	// }
  42.  
  43. 	// // update lên 
  44. 	// {
  45. 	// 	for (int i = 1; i <= n; i++) dp[i] = 1;   
  46.  
  47. 	// 	for (int i = 1; i < n; i++) {
  48. 	// 		for (int j = i + 1; j <= n; j++) {
  49. 	// 			if (a[j] > a[i]) dp[j] = max(dp[j], dp[i] + 1); 
  50. 	// 		}
  51. 	// 	}
  52. 	// }
  53.  
  54. 	// int ans = 0;  
  55. 	// for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);   
  56.  
  57. 	// cout << ans << '\n'; 
  58.  
  59. 	// đệ quy 
  60. 	{
  61. 		memset(memo, -1, sizeof memo);     
  62. 		int ans = 0;  
  63. 		for (int i = 1; i <= n; i++) ans = max(ans, f(i));   
  64.  
  65. 		cout << ans << '\n'; 
  66. 	}
  67. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
6
1 2 5 4 6 2
stdout
copy 
4
https://ideone.com/nY88Fc
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!