fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, arr[1000001], dp[1000001];
  6.  
  7. int ans() {
  8. 	dp[1] = 1;
  9.  
  10. 	for (int i = 2; i <= n; i ++) {
  11. 		// dp[i] musi byc minimum 1, a tablica zadeklarowana
  12. 		// globalnie ma zera we wszystkich szufladkach tablicy
  13. 		dp[i] ++;
  14.  
  15. 		// szukam max posrod wszystkich dp[j] takich,
  16. 		// ze j < i oraz arr[j] < arr[i]
  17. 		int mx = 0;
  18. 		for (int j = 1; j < i; j ++) {
  19. 			if (arr[j] < arr[i])
  20. 				mx = max(mx, dp[j]);
  21. 		}
  22.  
  23. 		// powiekszam dp[i] (ktore btw jest rowne 1) o max
  24. 		// sposrod dp[j] gdzie j < i oraz arr[j] < arr[i]
  25. 		// UWAGA! mx moze byc rowne 0 i wtedy dp[i] pozostanie 1
  26. 		dp[i] += mx;
  27. 	}
  28.  
  29. 	// szukam max wsrod wszystkich dp[i], 1 <= i <= 1e6
  30. 	int mx = dp[1];
  31. 	for (int i = 2; i <= n; i ++)
  32. 		mx = max(mx, dp[i]);
  33.  
  34. 	return mx;
  35. }
  36.  
  37. int main() {
  38. 	ios_base::sync_with_stdio(0);
  39. 	cin.tie(0); cout.tie(0);
  40.  
  41. 	cin >> n;
  42.  
  43. 	for (int i = 1; i <= n; i ++)
  44. 		cin >> arr[i];
  45.  
  46. 	cout << ans();
  47. }
Success #stdin #stdout 0.01s 5708KB
comments (?)
stdin
copy 
5
1 0 2 1 2
stdout
copy 
3
https://ideone.com/pEsxiN
language:
C++14 (clang 8.0)
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!