fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // O(N^3) naive
  5. int solveNaive(vector<int> v) {
  6. 	const int n = v.size();
  7. 	int ans = 0;
  8. 	for (int i = 0; i < n; i++) {
  9. 		for (int j = i; j < n; j++) {
  10. 			unordered_map<int, int> cnt;
  11. 			int max_cnt = 0;
  12. 			for (int k = i; k <= j; k++) {
  13. 				cnt[v[k]]++;
  14. 				max_cnt = max(max_cnt, cnt[v[k]]);
  15. 			}
  16. 			if (max_cnt >= j-i-2) {
  17. 				ans = max(ans, j-i+1);
  18. 			}
  19. 		}
  20. 	}
  21. 	return ans;
  22. }
  23.  
  24. // O(N^2) naive
  25. int solveNaiveLittleOpt(vector<int> v) {
  26. 	const int n = v.size();
  27. 	int ans = 0;
  28. 	for (int i = 0; i < n; i++) {
  29. 		unordered_map<int, int> cnt;
  30. 		int max_cnt = 0;
  31. 		for (int j = i; j < n; j++) {
  32. 			cnt[v[j]]++;
  33. 			max_cnt = max(max_cnt, cnt[v[j]]);
  34. 			if (max_cnt >= j-i-2) {
  35. 				ans = max(ans, j-i+1);
  36. 			}
  37. 		}
  38. 	}
  39. 	return ans;
  40. }
  41.  
  42. // O(NlgN)
  43. int solve(vector<int> v) {
  44. 	unordered_map<int, int> cnt;
  45. 	multiset<int> pq;
  46. 	const int n = v.size();
  47. 	int l = 0, r = 0;
  48. 	int ans = 0;
  49. 	while (r < n) {
  50. 		cnt[v[r]]++;
  51. 		pq.insert(cnt[v[r]]);
  52. 		while(*pq.rbegin() < r-l-2) {
  53. 			auto iter = pq.find(cnt[v[l]]);
  54. 			pq.erase(iter);
  55. 			cnt[v[l]]--;
  56. 			pq.insert(cnt[v[l]]);
  57. 			l++;
  58. 		}
  59. 		ans = max(ans, r-l+1);
  60. 		r++;
  61. 	}
  62. 	return ans;
  63. }
  64.  
  65. // O(N) given element of v is in [-10, 10]
  66. int solveOpt(vector<int> v) {
  67. 	vector<int> cnt(21, 0);
  68. 	multiset<int> pq;
  69. 	const int n = v.size();
  70. 	int l = 0, r = 0;
  71. 	int ans = 0;
  72. 	while (r < n) {
  73. 		cnt[v[r]+10]++;
  74. 		while(*max_element(cnt.begin(), cnt.end()) < r-l-2) {
  75. 			cnt[v[l]+10]--;
  76. 			l++;
  77. 		}
  78. 		ans = max(ans, r-l+1);
  79. 		r++;
  80. 	}
  81. 	return ans;
  82. }
  83.  
  84. int main() {
  85. 	cout<<solveOpt({-9, 8})<<endl;
  86. 	cout<<solveOpt({1, 1, -10, 3, -10, 3, -10})<<endl;
  87. 	cout<<solveOpt({2, 3, 3, 3, 3, 1})<<endl;
  88. 	cout<<solveOpt({3, 3, 2, 1, 2, 2, 9, 3, 3})<<endl;
  89. 	return 0;
  90. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
6
6
6
https://ideone.com/N7Sqez
language:
C++14 (gcc 8.3)
created:
1 day 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!